JavaScript中的排列?

我试图写一个函数,执行以下操作:

  • 以一个整数数组作为参数(例如[1,2,3,4])
  • 创build了[1,2,3,4]的所有可能排列的arrays,每个排列的长度为4

下面的函数(我在网上find它)通过把一个string作为参数来做到这一点,并返回该string的所有排列

我无法弄清楚如何修改它以使其与整数数组一起工作(我认为这与某些方法在string上的工作方式不同于整数方法有关,但我不确定。 ..)

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 }; 

注:我正在寻找使函数返回整数数组, 而不是一个string数组。

我真的需要解决scheme在JavaScript中。 我已经想出了如何在Python中做到这一点

如果你注意到,代码在做任何排列之前实际上将字符分割成一个数组,所以你只需要移除join和split操作

 var permArr = [], usedChars = []; function permute(input) { var i, ch; for (i = 0; i < input.length; i++) { ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } permute(input); input.splice(i, 0, ch); usedChars.pop(); } return permArr }; document.write(JSON.stringify(permute([5, 3, 7, 1]))); 

迟到了,但在这里添加一个稍微优雅的版本。 可以是任何数组…

 function permutator(inputArr) { var results = []; function permute(arr, memo) { var cur, memo = memo || []; for (var i = 0; i < arr.length; i++) { cur = arr.splice(i, 1); if (arr.length === 0) { results.push(memo.concat(cur)); } permute(arr.slice(), memo.concat(cur)); arr.splice(i, 0, cur[0]); } return results; } return permute(inputArr); } 

添加一个ES6(2015)版本。 也不会改变原来的input数组。 在Chrome中的控制台中工作…

 const permutator = (inputArr) => { let result = []; const permute = (arr, m = []) => { if (arr.length === 0) { result.push(m) } else { for (let i = 0; i < arr.length; i++) { let curr = arr.slice(); let next = curr.splice(i, 1); permute(curr.slice(), m.concat(next)) } } } permute(inputArr) return result; } 

所以…

 permutator(['c','a','t']); 

产量…

 [ [ 'c', 'a', 't' ], [ 'c', 't', 'a' ], [ 'a', 'c', 't' ], [ 'a', 't', 'c' ], [ 't', 'c', 'a' ], [ 't', 'a', 'c' ] ] 

和…

 permutator([1,2,3]); 

产量…

 [ [ 1, 2, 3 ], [ 1, 3, 2 ], [ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ] ] 
 var inputArray = [1, 2, 3]; var result = inputArray.reduce(function permute(res, item, key, arr) { return res.concat(arr.length > 1 && arr.slice(0, key).concat(arr.slice(key + 1)).reduce(permute, []).map(function(perm) { return [item].concat(perm); }) || item); }, []); alert(JSON.stringify(result)); 

以下非常有效的algorithm使用Heap的方法来生成所有在O(N!)中运行时复杂度为N的元素的排列:

 function permute(permutation) { var length = permutation.length, result = [permutation.slice()], c = new Array(length).fill(0), i = 1, k, p; while (i < length) { if (c[i] < i) { k = i % 2 && c[i]; p = permutation[i]; permutation[i] = permutation[k]; permutation[k] = p; ++c[i]; i = 1; result.push(permutation.slice()); } else { c[i] = 0; ++i; } } return result; } console.log(permute([1, 2, 3])); 

我已经改善了四甘腾的答案 。

现在可以多次调用permArr ,因为permArrusedChars都被清除。

 function permute(input) { var permArr = [], usedChars = []; return (function main() { for (var i = 0; i < input.length; i++) { var ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } main(); input.splice(i, 0, ch); usedChars.pop(); } return permArr; })(); } 
 function permute(input) { var permArr = [], usedChars = []; return (function main() { for (var i = 0; i < input.length; i++) { var ch = input.splice(i, 1)[0]; usedChars.push(ch); if (input.length == 0) { permArr.push(usedChars.slice()); } main(); input.splice(i, 0, ch); usedChars.pop(); } return permArr; })(); } document.write(JSON.stringify(permute([5, 3, 7, 1]))); 

以下函数将置换任何types的数组,并在每个find的排列上调用指定的callback函数:

 /* Permutate the elements in the specified array by swapping them in-place and calling the specified callback function on the array for each permutation. Return the number of permutations. If array is undefined, null or empty, return 0. NOTE: when permutation succeeds, the array should be in the original state on exit! */ function permutate(array, callback) { // Do the actual permuation work on array[], starting at index function p(array, index, callback) { // Swap elements i1 and i2 in array a[] function swap(a, i1, i2) { var t = a[i1]; a[i1] = a[i2]; a[i2] = t; } if (index == array.length - 1) { callback(array); return 1; } else { var count = p(array, index + 1, callback); for (var i = index + 1; i < array.length; i++) { swap(array, i, index); count += p(array, index + 1, callback); swap(array, i, index); } return count; } } if (!array || array.length == 0) { return 0; } return p(array, 0, callback); } 

如果你这样称呼它:

  // Empty array to hold results var result = []; // Permutate [1, 2, 3], pushing every permutation onto result[] permutate([1, 2, 3], function (a) { // Create a copy of a[] and add that to result[] result.push(a.slice(0)); }); // Show result[] document.write(result); 

我认为这将完成你所需要的 – 用数组[1,2,3]填充一个名为result的数组。 结果是:

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

JSFiddle上稍微更清晰的代码: http : //jsfiddle.net/MgmMg/6/

无需外部数组或附加function的答案

 function permutator (arr) { var permutations = []; if (arr.length === 1) { return [ arr ]; } for (var i = 0; i < arr.length; i++) { var subPerms = permutator(arr.slice(0, i).concat(arr.slice(i + 1))); for (var j = 0; j < subPerms.length; j++) { subPerms[j].unshift(arr[i]); permutations.push(subPerms[j]); } } return permutations; } 

这个问题的大部分答案都使用昂贵的操作,如连续插入和删除数组中的项目,或者反复拷贝数组。

相反,这是典型的回溯解决scheme:

 function permute(arr) { var results = [], l = arr.length, used = Array(l), // Array of bools. Keeps track of used items data = Array(l); // Stores items of the current permutation (function backtracking(pos) { if(pos == l) return results.push(data.slice()); for(var i=0; i<l; ++i) if(!used[i]) { // Iterate unused items used[i] = true; // Mark item as used data[pos] = arr[i]; // Assign item at the current position backtracking(pos+1); // Recursive call used[i] = false; // Mark item as not used } })(0); return results; } 
 permute([1,2,3,4]); // [ [1,2,3,4], [1,2,4,3], /* ... , */ [4,3,2,1] ] 

由于结果数组很大,因此逐个迭代结果可能是一个好主意,而不是同时分配所有数据。 在ES6中,这可以通过发生器完成:

 function permute(arr) { var l = arr.length, used = Array(l), data = Array(l); return function* backtracking(pos) { if(pos == l) yield data.slice(); else for(var i=0; i<l; ++i) if(!used[i]) { used[i] = true; data[pos] = arr[i]; yield* backtracking(pos+1); used[i] = false; } }(0); } 
 var p = permute([1,2,3,4]); p.next(); // {value: [1,2,3,4], done: false} p.next(); // {value: [1,2,4,3], done: false} // ... p.next(); // {value: [4,3,2,1], done: false} p.next(); // {value: undefined, done: true} 

从Haskell的启发一些版本:

 perms [] = [[]] perms xs = [ x:ps | x <- xs , ps <- perms ( xs\\[x] ) ] 
 function perms(xs){ if (!xs.length) return [[]]; var r=[]; for (var i=0;i<xs.length;i++){ var xs_ = xs.slice(), x = xs_.splice(i, 1), ps = perms(xs_); r.push(...ps.map(p=>x.concat(p))) } return r; } document.write(JSON.stringify(perms([1,2,3]))); 

这是另一个“更多recursion”解决scheme。

 function perms(input) { var data = input.slice(); var permutations = []; var n = data.length; if (n === 0) { return [ [] ]; } else { var first = data.shift(); var words = perms(data); words.forEach(function(word) { for (var i = 0; i < n; ++i) { var tmp = word.slice(); tmp.splice(i, 0, first) permutations.push(tmp); } }); } return permutations; } var str = 'ABC'; var chars = str.split(''); var result = perms(chars).map(function(p) { return p.join(''); }); console.log(result); 
  function perm(xs) { return xs.length === 0 ? [[]] : perm(xs.slice(1)).reduce(function (acc, ys) { for (var i = 0; i < xs.length; i++) { acc.push([].concat(ys.slice(0, i), xs[0], ys.slice(i))); } return acc; }, []); } 

testing它:

 console.log(JSON.stringify(perm([1, 2, 3,4]))); 

这是一个有趣的任务,这里是我的贡献。 这非常简单快捷。 如果有兴趣请与我联系,并阅读。

如果你想快速完成这项工作,你一定要进入dynamic编程。 这意味着你应该忘记recursion方法。 这是肯定的…

好的le_m使用Heap方法的代码似乎是迄今为止最快的代码 。 那么我没有得到我的algorithm的名称,我不知道它是否已经实施或不是,但它非常简单和快速。 就像所有的dynamic编程方法一样,我们将从最简单的问题开始,然后进行最终的结果。

假设我们有一个数组a = [1,2,3]我们将开始

 r = [[1]]; // result t = []; // interim result 

然后按照这三个步骤;

  1. 对于我们的r (结果)数组中的每个项目,我们将添加input数组的下一个项目。
  2. 我们将旋转每个项目的长度多次,并将每个实例存储在临时结果数组t 。 (除了第一个不浪费时间0转)
  3. 一旦我们完成了所有的项目,临时数组t应该保持下一级的结果,所以我们使r = t; t = []; r = t; t = []; 并进行到input数组a的长度为止。

所以下面是我们的步骤;

 r array t array [[1,2]] [[1,2], [2,1]] [[1,2],[2,1]] [[1,2,3],[2,3,1],[3,1,2], [2,1,3],[1,3,2],[3,2,1]] 

所以这里是代码

 function perm(a){ var r = [[a[0]]], t = [], s = []; if (a.length <= 1) return a; for (var i = 1, la = a.length; i < la; i++){ for (var j = 0, lr = r.length; j < lr; j++){ r[j].push(a[i]); t.push(r[j]); for(var k = 1, lrj = r[j].length; k < lrj; k++){ for (var l = 0; l < lrj; l++) s[l] = r[j][(k+l)%lrj]; t[t.length] = s; s = []; } } r = t; t = []; } return r; } var arr = [0,1,2,4,5]; console.log("The length of the permutation is:",perm(arr).length); console.time("Permutation test"); for (var z = 0; z < 2000; z++) perm(arr); console.timeEnd("Permutation test"); 

类似于@crl的Haskell风格的解决scheme,但是使用reduce

 function permutations( base ) { if (base.length == 0) return [[]] return permutations( base.slice(1) ).reduce( function(acc,perm) { return acc.concat( base.map( function(e,pos) { var new_perm = perm.slice() new_perm.splice(pos,0,base[0]) return new_perm })) },[]) } 

我对网站的第一个贡献。 在这里查看代码背后algorithm的一些解释图。 另外,根据我所做的testing,这个代码运行得比这个date之前提到的所有其他方法都要快,当然,如果数值很less,那么这个代码是最小的,但是当添加太多时,时间会成倍增加。

 var permutations2 = function (arr) { var finalArr = []; var iterator = function (arrayTaken, tree) { for (var i = 0; i < tree; i++) { var temp = arrayTaken.slice(); temp.splice(tree - 1 - i, 0, temp.splice(tree - 1, 1)[0]); if (tree >= arr.length) { finalArr.push(temp); } else { iterator(temp, tree + 1); } } } iterator(arr, 1); return finalArr; }; 

我写了一篇文章来演示如何在JavaScript中排列数组。 这是做这个的代码。

 var count=0; function permute(pre,cur){ var len=cur.length; for(var i=0;i<len;i++){ var p=clone(pre); var c=clone(cur); p.push(cur[i]); remove(c,cur[i]); if(len>1){ permute(p,c); }else{ print(p); count++; } } } function print(arr){ var len=arr.length; for(var i=0;i<len;i++){ document.write(arr[i]+" "); } document.write("<br />"); } function remove(arr,item){ if(contains(arr,item)){ var len=arr.length; for(var i = len-1; i >= 0; i--){ // STEP 1 if(arr[i] == item){ // STEP 2 arr.splice(i,1); // STEP 3 } } } } function contains(arr,value){ for(var i=0;i<arr.length;i++){ if(arr[i]==value){ return true; } } return false; } function clone(arr){ var a=new Array(); var len=arr.length; for(var i=0;i<len;i++){ a.push(arr[i]); } return a; } 

打电话

置换([],[1,2,3,4])

将工作。 有关如何工作的详细信息,请参阅该文章中的解释。

 function nPr(xs, r) { if (!r) return []; return xs.reduce(function(memo, cur, i) { var others = xs.slice(0,i).concat(xs.slice(i+1)), perms = nPr(others, r-1), newElms = !perms.length ? [[cur]] : perms.map(function(perm) { return [cur].concat(perm) }); return memo.concat(newElms); }, []); } 
 "use strict"; function getPermutations(arrP) { var results = []; var arr = arrP; arr.unshift(null); var length = arr.length; while (arr[0] === null) { results.push(arr.slice(1).join('')); let less = null; let lessIndex = null; for (let i = length - 1; i > 0; i--) { if(arr[i - 1] < arr[i]){ less = arr[i - 1]; lessIndex = i - 1; break; } } for (let i = length - 1; i > lessIndex; i--) { if(arr[i] > less){ arr[lessIndex] = arr[i]; arr[i] = less; break; } } for(let i = lessIndex + 1; i<length; i++){ for(let j = i + 1; j < length; j++){ if(arr[i] > arr[j] ){ arr[i] = arr[i] + arr[j]; arr[j] = arr[i] - arr[j]; arr[i] = arr[i] - arr[j]; } } } } return results; } var res = getPermutations([1,2,3,4,5]); var out = document.getElementById('myTxtArr'); res.forEach(function(i){ out.value+=i+', '}); 
 textarea{ height:500px; width:500px; } 
 <textarea id='myTxtArr'></textarea> 
  let permutations = [] permutate([], { color: ['red', 'green'], size: ['big', 'small', 'medium'], type: ['saison', 'oldtimer'] }) function permutate (currentVals, remainingAttrs) { remainingAttrs[Object.keys(remainingAttrs)[0]].forEach(attrVal => { let currentValsNew = currentVals.slice(0) currentValsNew.push(attrVal) if (Object.keys(remainingAttrs).length > 1) { let remainingAttrsNew = JSON.parse(JSON.stringify(remainingAttrs)) delete remainingAttrsNew[Object.keys(remainingAttrs)[0]] permutate(currentValsNew, remainingAttrsNew) } else { permutations.push(currentValsNew) } }) } 

结果:

 [ [ 'red', 'big', 'saison' ], [ 'red', 'big', 'oldtimer' ], [ 'red', 'small', 'saison' ], [ 'red', 'small', 'oldtimer' ], [ 'red', 'medium', 'saison' ], [ 'red', 'medium', 'oldtimer' ], [ 'green', 'big', 'saison' ], [ 'green', 'big', 'oldtimer' ], [ 'green', 'small', 'saison' ], [ 'green', 'small', 'oldtimer' ], [ 'green', 'medium', 'saison' ], [ 'green', 'medium', 'oldtimer' ] ] 

大多数其他答案不利用新的JavaScript生成器function,这是一个完美的解决scheme,这种types的问题。 内存中可能只需要一个排列。 另外,我更喜欢生成一系列索引的排列,因为这使我可以对每个排列进行索引,并跳转到任何特定的排列,也可以用来排列其他任何排列。

 // ES6 generator version of python itertools [permutations and combinations] const range = function*(l) { for (let i = 0; i < l; i+=1) yield i; } const isEmpty = arr => arr.length === 0; const permutations = function*(a) { const r = arguments[1] || []; if (isEmpty(a)) yield r; for (let i of range(a.length)) { const aa = [...a]; const rr = [...r, ...aa.splice(i, 1)]; yield* permutations(aa, rr); } } console.log('permutations of ABC'); console.log(JSON.stringify([...permutations([...'ABC'])])); const combinations = function*(a, count) { const r = arguments[2] || []; if (count) { count = count - 1; for (let i of range(a.length - count)) { const aa = a.slice(i); const rr = [...r, ...aa.splice(0, 1)]; yield* combinations(aa, count, rr); } } else { yield r; } } console.log('combinations of 2 of ABC'); console.log(JSON.stringify([...combinations([...'ABC'], 2)])); const permutator = function() { const range = function*(args) { let {begin = 0, count} = args; for (let i = begin; count; count--, i+=1) { yield i; } } const factorial = fact => fact ? fact * factorial(fact - 1) : 1; return { perm: function(n, permutationId) { const indexCount = factorial(n); permutationId = ((permutationId%indexCount)+indexCount)%indexCount; let permutation = [0]; for (const choiceCount of range({begin: 2, count: n-1})) { const choice = permutationId % choiceCount; const lastIndex = permutation.length; permutation.push(choice); permutation = permutation.map((cv, i, orig) => (cv < choice || i == lastIndex) ? cv : cv + 1 ); permutationId = Math.floor(permutationId / choiceCount); } return permutation.reverse(); }, perms: function*(n) { for (let i of range({count: factorial(n)})) { yield this.perm(n, i); } } }; }(); console.log('indexing type permutator'); let i = 0; for (let elem of permutator.perms(3)) { console.log(`${i}: ${elem}`); i+=1; } console.log(); console.log(`3: ${permutator.perm(3,3)}`); 
 #!/usr/bin/env node "use strict"; function perm(arr) { if(arr.length<2) return [arr]; var res = []; arr.forEach(function(x, i) { perm(arr.slice(0,i).concat(arr.slice(i+1))).forEach(function(a) { res.push([x].concat(a)); }); }); return res; } console.log(perm([1,2,3,4])); 

这是map / reduce的一个非常好的用例:

 function permutations(arr) { if (arr.length === 1) return arr; return arr.reduce((acc, cv) => { let remaining = [...arr]; remaining.splice(remaining.indexOf(cv), 1); return acc.concat(permutations(remaining).map(a => [cv, ...a])); }, []); } 
  • 首先,我们处理基本情况,如果只有其中的项目,只需返回数组
  • 在所有其他情况下
    • 我们创build一个空数组
    • 循环input数组
    • and add an array of the current value und all permutations of the remaining array [cv, ...a]

Here's a very short solution, that only works for 1 or 2 long strings. It's a oneliner, and it's blazing fast, using ES6 and not depending on jQuery. 请享用:

 var p = l => l.length<2 ? [l] : l.length==2 ? [l[0]+l[1],l[1]+l[0]] : Function('throw Error("unimplemented")')(); 
 function swap(array1, index1, index2) { var temp; temp = array1[index1]; array1[index1] = array1[index2]; array1[index2] = temp; } function permute(a, l, r) { var i; if (l == r) { console.log(a.join('')); } else { for (i = l; i <= r; i++) { swap(a, l, i); permute(a, l + 1, r); swap(a, l, i); } } } permute(["A","B","C", "D"],0,3); 

// sample execution //for more details refer this link

// http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/