PHP实现排列组合算法

一、组合算法

给定一非重复字符串所有的组合，形如 abc，则
Q1：输出所有组合 a，b，c，ab，ac，bc，abc；
Q2：输出指定长度的组合，如2个长度则输出 ab，ac，bc；
Q3：计算组合总数。

1、组合算法一——获取所有组合

/**
 * get_combinations 获取指定字符串的所有组合
 * @param string $str 目标字符串
 * @param array $comb 组合容器
 * @return bool | array
 * @author Mike Lee
 */
function get_combinations($str = '', &$comb = array())
{
    if (trim($str) == '' || ! $str) return false;
    if (strlen($str) <= 1) {
        $comb[] = $str;
    } else {
        $str_first = $str[0];
        $comb_temp = get_combinations(substr($str, 1), $comb);
        $comb[] = $str_first;
        foreach ($comb_temp as $k => $v) {
            $comb[] = $str_first . $v;
        }
    }
    return $comb;
}

2、组合算法二——获取指定长度的组合

待更新

3、组合算法三——计算组合数

/**
 * count_combinations 计算组合数
 * @param int $n
 * @param int $m
 * @return int $count
 * @author Mike Lee
 */
function count_combinations($n= 1, $m = false)
{
    $n = (int) $n;
    if ($n < 0) return false;
    if ($m === false) {
        $count = pow(2, $n) - 1;
    } else {
        $m = (int) $m;
        if ($m < 0) return false;
        if ($m > $n) return false;
        if ($m == $n || $m == 0) {
            $count = 1;
        } else {
            $count = factorial($n) / (factorial($m) * factorial($n - $m));
        }
    }
    return $count;
}

/**
 * factorial 阶乘
 * @param int $num
 * @return int $result
 */
function factorial($num = 0)
{
    $num = (int) $num;
    if ($num < 0) return false; // 负数没有阶乘
    if ($num > 1) {
        $result = $num * factorial($num - 1);
    } else {
        $result = 1;    // 0和1的阶乘均为1
    }
    return $result;
}

4、组合算法四——数组组合

给定若干一维索引数组，对各数组中的值进行组合；
例如 $a = [1, 2]，$b = ['a', 'b']，那么将有如下组合：
[1, 'a']，[1, 'b']，[2, 'a']，[2, 'b']；
下面算法实现 foo 和 foo2 函数只是传参不同，效果一致。

function foo(array $arr)
{
    $num = count($arr);
    if ($num === 0) return false;
    if ($num === 1) return $arr[0];

    while(count($arr) > 1) {
        $arr_first = array_shift($arr);
        $arr_second = array_shift($arr);
        $c = array();
        foreach ($arr_first as $v) {
            $v = (array) $v;
            foreach ($arr_second as $val) {
                $c[] = array_merge($v, (array) $val);
            }
        }
        array_unshift($arr, $c);
        unset($c);
    }
    return $arr[0];
}

function foo2()
{
    $num = func_num_args();
    if ($num === 0) return false;
    $all = func_get_args();
    if ($num === 1) return $all[0];
    while(count($all) > 1) {
        $all_first = array_shift($all);
        $all_second = array_shift($all);
        $c = array();
        foreach ($all_first as $v) {
            $v = (array) $v;
            foreach ($all_second as $val) {
                $c[] = array_merge($v, (array) $val);
            }
        }
        array_unshift($all, $c);
        unset($c);
    }
    return $all[0];
}

二、排列算法

给定字符串一非重复字符串，例如 abc，则
Q1：输出所有排列 a，b，c，ab，ac，ba，bc，ca，cb，abc，acb，bac，bca，cab，cba；
Q2：输出指定长度的排列，如2个长度则输出 ab，ac，ba，bc，ca，cb；
Q3：计算排列总数。

1、排列算法一——获取所有排列

待更新