组合算法JS/PHP实现

原创
2017/03/09 16:57
阅读数 226

来个组合算法:将Haskell算法试着翻译成JS/PHP,纯递归实现. Haskell代码:

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
分享
返回顶部
顶部