JS、PHP全排列permutation算法,一行代码实现。

原创
2017/03/10 18:41
阅读数 900

写递归算法,最好的是Haskell,写好Haskell代码,照样翻译成JS即可。

Haskell全排列算法:

permute :: Eq a => [a] -> [[a]]
permute [] = [[]]
permute xs = concatMap (\x -> map (x:) $ permute $ delete x xs) xs
                            
main = do
    print $ permute [1..3]

输出:

[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

concatMap 函数实现为:

concatMap' f = foldr ((++) . f) []

concatMap功能为,先map,map完成后,将所有元素连接在一起,拼接成一个数组,如map返回 [[[1,2]],[[2,1]]] 这两个元素,拼接后则为:[[1,2],[2,1]],相当于作了一次flat。

翻译成JS:

function permutation(ls) {
  return ls.length ? ls.reduce((acc, x) => acc.concat(permutation(ls.filter(e => e != x)).map(a => [x].concat(a))), []) : [[]];
}
console.log(permutation([1, 2, 3]));

输出:

[ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]

原理,如果迭代到最后一次,返回一个二维空数组,否则: reduce遍历每一项,传入初始空数组,然后累加器acc负责将二维数组拼接在一起,内部传入迭代规则: 除去本次reduce迭代的元素x剩下元素求permutation递归,求完后,将x加入到每一个返回的小数组前面, 完成 Haskell map (x:) $ permute $ delete x xs 代码功能。 reduce中的acc.concat则完成 concatMap 功能。

PHP代码翻译:

//可以将三目运算符拆封成一个if,更加易懂。
function permute($array) {
    return count($array) ? array_reduce($array, function($acc, $x) use($array) {
        return array_merge($acc, array_map(function($a) use($x) { return array_merge([$x], $a);  }, permute(array_filter($array, function($v) use($x) { return $v != $x; }))));
    }, []) : [[]];
}
print_r(permute([1,2,3]));
echo json_encode(permute([1,2,3]))."\n";

输出:

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

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

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

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

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

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

)
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

转换成JSON,可以看得更简洁点。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部