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 ，因为permArr和usedChars都被清除。
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
然后按照这三个步骤;
- 对于我们的
r（结果）数组中的每个项目，我们将添加input数组的下一个项目。 - 我们将旋转每个项目的长度多次，并将每个实例存储在临时结果数组
t。 （除了第一个不浪费时间0转） - 一旦我们完成了所有的项目，临时数组
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/
