排列和组合问题的PHP实现

1.排列

给定一个字符串，比如：abcd，输出这个字符串的所有排列。

/**
 * 交换值
 * @param $a
 * @param $b
 */
function switchPos(&$str, $a, $b)
{
    $tmp = $str[$a];
    $str[$a] = $str[$b];
    $str[$b] = $tmp;
}

/**
 * 排列
 */
function Permutation($str, $len, $begin, &$result)
{
    if($len <= 0) return $result;
    if($len - $begin < 2) {
        $result[] = $str;
    } else {
        for($i = $begin; $i < $len; $i ++)
        {
            if($i != $begin && $str[$begin] == $str[$i]) continue;
            switchPos($str, $begin, $i);
            Permutation($str, $len, $begin + 1, $result);
            switchPos($str, $begin, $i);
        }
    }
}

2. 组合

给定一个字符串，比如：abcd，输出这个字符串的所有组合。

/**
 * 组合
 * @param $str
 * @param $result
 */
function Combination($str, &$result)
{
    $len = strlen($str);
    $cache = [];
    for($i = 1; $i <= $len; $i ++)
    {
        Combine($str, 0, $i, $cache, $result);
    }
}

/**
 * 组合操作
 * @param $str
 * @param $begin
 * @param $number
 * @param $cache
 * @param $result
 */
function Combine($str, $begin, $number, &$cache, &$result)
{
    if($number == 0) {
        $element = implode('', $cache);
        $result[] = $element;
        return;
    }
    if($begin >= strlen($str)) return;
    array_push($cache, $str[$begin]);
    Combine($str, $begin + 1, $number - 1, $cache, $result);
    array_pop($cache);
    Combine($str, $begin + 1, $number, $cache, $result);
}