查找JavaScript数组值的所有组合

如何在N个可变长度的JavaScript数组中生成所有的值组合?

比方说,我有N个JavaScript数组,例如

var first = ['a', 'b', 'c', 'd']; var second = ['e']; var third = ['f', 'g', 'h', 'i', 'j']; 

(在这个例子中是三个数组,但是它的N个数组是针对这个问题的。)

我想要输出他们的价值的所有组合,产生

 aef aeg aeh aei aej bef beg .... dej 

编辑:这是我工作的版本,使用朋友接受的答案作为基础。

 var allArrays = [['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]; function allPossibleCases(arr) { if (arr.length === 0) { return []; } else if (arr.length ===1){ return arr[0]; } else { var result = []; var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array for (var c in allCasesOfRest) { for (var i = 0; i < arr[0].length; i++) { result.push(arr[0][i] + allCasesOfRest[c]); } } return result; } } var r=allPossibleCases(allArrays); //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"] 

这不是排列,请参阅维基百科的排列定义 。

但你可以用recursion来实现这个:

 var allArrays = [['a', 'b'], ['c'], ['d', 'e', 'f']] function allPossibleCases(arr) { if (arr.length == 1) { return arr[0]; } else { var result = []; var allCasesOfRest = allPossibleCases(arr.slice(1)); // recur with the rest of array for (var i = 0; i < allCasesOfRest.length; i++) { for (var j = 0; j < arr[0].length; j++) { result.push(arr[0][j] + allCasesOfRest[i]); } } return result; } } 

你也可以使用循环,但是它会有点棘手,需要实现你自己的堆栈模拟。

你不需要recursion或嵌套循环,甚至不需要在内存中生成/存储整个排列数组。

由于排列的数量是每个数组的长度的乘积(调用这个numPerms ),您可以创build一个函数getPermutation(n) ,通过计算所需的索引,返回索引0numPerms - 1之间的唯一排列根据n检索它的字符。

这是怎么做的? 如果你想在每个包含[0,1,2,… 9]的数组上创build排列,那么它非常简单……第245个排列(n = 245)是“245”,相当直观,或者:

 arrayHundreds[Math.floor(n / 100) % 10] + arrayTens[Math.floor(n / 10) % 10] + arrayOnes[Math.floor(n / 1) % 10] 

问题的复杂性在于数组大小不同。 我们可以通过用其他除数replacen/100n/10等来解决这个问题。 为此,我们可以很容易地预先计算一系列除数。 在上面的例子中,100的除数等于arrayTens.length * arrayOnes.length 。 因此,我们可以计算给定数组的除数为剩余数组长度的乘积。 最后一个数组总是有1的除数。另外,我们用当前数组的长度来修改而不是10。

示例代码如下:

 var allArrays = [first, second, third, ...]; // Pre-calculate divisors var divisors = []; for (var i = allArrays.length - 1; i >= 0; i--) { divisors[i] = divisors[i + 1] ? divisors[i + 1] * allArrays[i + 1].length : 1; } function getPermutation(n) { var result = "", curArray; for (var i = 0; i < allArrays.length; i++) { curArray = allArrays[i]; result += curArray[Math.floor(n / divisors[i]) % curArray.length]; } return result; } 

提供的答案看起来对我来说太难了。 所以我的解决scheme是:

 var allArrays = new Array(['a', 'b'], ['c', 'z'], ['d', 'e', 'f']); function getPermutation(array, prefix) { prefix = prefix || ''; if (!array.length) { return prefix; } var result = array[0].reduce(function (result, value) { return result.concat(getPermutation(array.slice(1), prefix + value)); }, []); return result; } console.log(getPermutation(allArrays)); 

你可以使用一个典型的回溯:

 function cartesianProductConcatenate(arr) { var data = new Array(arr.length); return (function* recursive(pos) { if(pos === arr.length) yield data.join(''); else for(var i=0; i<arr[pos].length; ++i) { data[pos] = arr[pos][i]; yield* recursive(pos+1); } })(0); } 

我使用了生成器函数来避免同时分配所有的结果,但是如果你想的话可以

 [...cartesianProductConcatenate([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']])]; // ["acd","ace","acf","azd","aze","azf","bcd","bce","bcf","bzd","bze","bzf"] 

我build议一个简单的recursion生成器函数如下:

 // Generate all combinations of array elements: function* combinations(head, ...tail) { let remainder = tail.length ? combinations(...tail) : [[]]; for (let r of remainder) for (let h of head) yield [h, ...r]; } // Example: let first = ['a', 'b', 'c', 'd']; let second = ['e']; let third = ['f', 'g', 'h', 'i', 'j']; for (let c of combinations(first, second, third)) { console.log(...c); } 

le_m的答案的答案直接使用数组数组:

 function *combinations(arrOfArr) { let [head, ...tail] = arrOfArr let remainder = tail.length ? combinations(tail) : [[]]; for (let r of remainder) for (let h of head) yield [h, ...r]; } 

希望能节省一些时间。