我正在尝试编写一个执行以下操作的函数:
-
将整数数组作为参数(例如[1,2,3,4])
-
创建一个包含[1,2,3,4]所有可能排列的数组,每个排列的长度为4
下面的函数(我在网上找到)通过将一个字符串作为参数,然后返回该字符串的所有排列来完成此操作
我无法弄清楚如何修改它以使其与整数数组一起工作(我认为这与某些方法在字符串上的工作方式不同于在整数上的工作方式有关,但我不确定 . ..)
var permArr = [], usedChars = [];
function permute(input) {
var i, ch, chars = input.split("");
for (i = 0; i < chars.length; i++) {
ch = chars.splice(i, 1);
usedChars.push(ch);
if (chars.length == 0)
permArr[permArr.length] = usedChars.join("");
permute(chars.join(""));
chars.splice(i, 0, ch);
usedChars.pop();
}
return permArr
};
注意:我希望使函数返回整数数组, not 是一个字符串数组 .
我真的需要使用JavaScript的解决方案 . 我已经在python中找到了如何做到这一点
26 回答
如果您注意到,代码实际上会在执行任何排列之前将字符拆分为数组,因此您只需删除连接和拆分操作
不太晚,但想在这里添加一个稍微优雅的版本 . 可以是任何阵列......
添加ES6(2015)版本 . 也不会改变原始输入数组 . 适用于Chrome中的控制台......
所以...
产量...
和...
产量...
以下非常有效的算法使用Heap's method生成N个元素的所有排列,运行时复杂度为O(N!):
相同的算法实现为generator,空间复杂度为O(N):
性能比较
随意将您的实现添加到以下benchmark.js测试套件中:
Chrome 48的运行时结果:
99.152ms This algorithm
153.115ms MarkusT
401.255ms js-combinatorics
497.037ms Urielzen
925.669ms Oriol
1026.571ms SiGanteng
2529.841ms delimited
3992.622ms monkey
4514.665ms Oriol
我改进了SiGanteng的answer .
现在可以多次调用
permute
,因为每次都会清除permArr
和usedChars
.以下函数置换任何类型的数组,并在找到的每个排列上调用指定的回调函数:
如果你这样称呼它:
我认为它将完全符合您的需要 - 使用数组[1,2,3]的排列填充一个名为
result
的数组 . 结果是:关于JSFiddle的更清晰的代码:http://jsfiddle.net/MgmMg/6/
此问题的大多数答案都使用昂贵的操作,如连续插入和删除数组中的项目,或重复复制数组 .
相反,这是典型的回溯解决方案:
由于结果数组很大,因此逐个迭代结果而不是同时分配所有数据可能是个好主意 . 在ES6中,这可以通过生成器来完成:
无需外部阵列或附加功能即可接听
一些版本受Haskell启发:
这是一项有趣的任务,这是我的贡献 . 它非常简单快速 . 如果有兴趣请耐心等待并继续阅读 .
如果你想快速完成这项工作,你一定要进入动态编程 . 这意味着你应该忘记递归方法 . 这是肯定的...
OK le_m's code使用Heap 's method seems to be the fastest so far. Well i haven' t得到了我的算法的名称,我已经实现了或者没有实现,但它非常简单快速 . 与所有动态编程方法一样,我们将从最简单的问题开始,并寻找最终结果 .
假设我们有一个
a = [1,2,3]
数组,我们将开始然后按照这三个步骤;
对于
r
(result)数组的每一项,我们将添加输入数组的下一项 .我们将多次旋转每个项目的长度,并将每个实例存储在中间结果数组
t
中 . (除了第一个不浪费0转的时间)一旦我们完成
r
的所有项目,临时数组t
应该保持下一级别的结果,所以我们生成r = t; t = [];
并继续运行直到输入数组a
的长度 .以下是我们的步骤;
所以这是代码
在多次测试中,我已经看到它在25~35ms内解决了[0,1,2,3,4]的120次排列2000次 .
这是另一个“更递归”的解决方案 .
输出:
测试它:
与@crl的Haskell风格解决方案类似,但使用
reduce
:这是map / reduce的一个非常好的用例:
首先,我们处理基本情况,如果只有on项,则只返回数组它
在所有其他情况下
我们创建一个空数组
循环输入数组
并添加当前值的数组以及剩余数组的所有排列
[].concat(cv,a)
这是一个最小的ES6版本 . 可以从Lodash中拉出扁平且无功能的扁平状态 .
结果:
大多数其他答案都没有使用新的javascript生成器函数,这是解决此类问题的完美解决方案 . 你可能在内存中只需要一次排列 . 此外,我更喜欢生成一系列索引的排列,因为这允许我索引每个排列并直接跳转到任何特定的排列,以及用于排列任何其他集合 .
我写了一个post来演示如何在JavaScript中置换数组 . 这是执行此操作的代码 .
打电话吧
将工作 . 有关其工作原理的详细信息,请参阅该帖子中的说明 .
输出按字典顺序排列的排列 . 仅适用于数字 . 在其他情况下,您必须在第34行更改交换方法 .
结果:
我对该网站的第一次贡献 . 有关代码背后算法的一些说明图,请参阅here . 此外,根据我所做的测试,此代码比此日期之前提到的所有其他方法运行得更快,当然,如果值很少,则它是最小的,但是当添加太多时,时间会呈指数增长 .
这是一个非常简短的解决方案,仅适用于1或2个长字符串 . 它是一个oneliner,它使用ES6并且不依赖于jQuery,速度极快 . 请享用:
//示例执行//有关更多详细信息,请参阅此链接
// http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/