文档章节

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

hell0cat
 hell0cat
发布于 2017/03/10 18:41
字数 442
阅读 103
收藏 0

写递归算法,最好的是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,可以看得更简洁点。

© 著作权归作者所有

共有 人打赏支持
hell0cat
粉丝 37
博文 48
码字总数 24082
作品 0
徐汇
程序员
私信 提问
刷《一年半经验,百度、有赞、阿里面试总结》·手记

在掘金上看到了一位大佬发了一篇很详细的面试记录文章-《一年半经验,百度、有赞、阿里面试总结》,为了查漏补缺,抽空就详细做了下。(估计只有我这么无聊了哈哈哈) 有给出的或者有些不完善...

大灰狼的小绵羊哥哥
2018/12/03
0
0
算法题丨Next Permutation

描述 Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange ......

lancel0t
2018/04/17
0
0
【万能搜索】万能DFS之全排列(一)——普通算法

DFS相信大家都很熟悉,下面就给出一种用DFS实现的算法。 全排列 大家对于全排列是很熟悉的,比如123的全排列就有: 123 132 213 231 312 321 这六种。 现在,我们来设计一个算法,来求出所有...

qq_37656398
2017/12/03
0
0
JavaScript加密库Crypto-JS的使用

先来图片一张,看看效果(一个采用Crypto-JS实现的工具展示): CryptoJS (crypto.js) 为 JavaScript 提供了各种各样的加密算法。目前已支持的算法包括: MD5 SHA-1 SHA-256 AES Rabbit MAR...

王振威
2012/07/30
0
6
手机腾讯网前端框架 MT 2.0.1 发布

手机腾讯网前端框架 MT 2.1.0 发布 ============= 主要更新 ------------------------ 1. 优化编辑距离算法性能,混合使用chunk,lcs两种算法提升性能,并保持增量更新字符级别的精度 2. 更新...

卢勇福
2014/07/28
6K
12

没有更多内容

加载失败,请刷新页面

加载更多

rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
6
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
3
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
7
0
Chocolatey 在Window搭建一个开发环境

在看了(利用 Chocolatey 快速在 Windows 下搭建一个开发环境)后,准备从零开始 一、准备工作 1、用管理员权限启动:powershell,执行错误请参考(PowerShell因为在此系统中禁止执行脚本的解...

近在咫尺远在天涯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部