查找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) ，通过计算所需的索引，返回索引0和numPerms - 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/100 ， n/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]; }
希望能节省一些时间。
