# 组合算法JS/PHP实现

2017/03/09 16:57

comb :: Int -> [a] -> [[a]]

comb 0 _  = [[]]
comb _ [] = []
comb n (x:xs) = map (x:) (comb (n-1) xs) ++ comb n xs

main = do
print $comb 3 [1..4]  输出： [[1,2,3],[1,2,4],[1,3,4],[2,3,4]]  Javascrip纯递归 function comb(n, xs) { if (!n) return [[]]; if (!xs.length) return []; // comb n (hd:tl) = map (hd:) (comb (n-1) tl) ++ comb n tl let hd = xs[0]; let tl = xs.slice(1); return comb(n - 1, tl).map( t => [hd].concat(t)).concat(comb(n, tl)); } console.log(comb(3, [1, 2, 3, 4]));  输出： [ [ 1, 2, 3 ], [ 1, 2, 4 ], [ 1, 3, 4 ], [ 2, 3, 4 ] ]  Javascript循环+递归 function combs(n, array) { let temp = new Array(n); let comb = []; function rec(index, next) { for (let i = next; i < array.length; i++) { temp[index] = array[i]; if (index == n - 1) { comb.push([].concat(temp)); } else { rec(index + 1, i + 1); } } } rec(0, 0); return comb; }  PHP纯递归： function combs($n, $array) { if(!$n) return [[]];
if(!count($array)) return [];$hd = array_shift($array); return array_merge(array_map(function(&$v) use($hd) { array_unshift($v, $hd); return$v;
}, combs($n-1,$array)), combs($n,$array));
}

print_r(combs(3, [1,2,3,4]));


Array
(
[0] => Array
(
[0] => 1
[1] => 2
[2] => 3
)

[1] => Array
(
[0] => 1
[1] => 2
[2] => 4
)

[2] => Array
(
[0] => 1
[1] => 3
[2] => 4
)

[3] => Array
(
[0] => 2
[1] => 3
[2] => 4
)

)


PHP循环+递归实现：

function combs($n,$array) {
$ret = [];$tmp = [];
$len = count($array);
$rec = function ($index, $next) use (&$n, &$array, &$ret, &$tmp, &$len, &$rec) { for($i=$next;$i<$len;$i++){
$tmp[$index] = $array[$i];
if($index ==$n-1){
$ret[] =$tmp;
}else{
$rec($index+1, $i+1); } } };$rec(0, 0);
return \$ret;
}


PHP 匿名函数递归，要在use里引用函数变量名。

0 评论
1 收藏
0