查找 JavaScript 数组值的所有组合（笛卡尔积）

Question

查找 JavaScript 数组值的所有组合（笛卡尔积）

74

我如何生成变长的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

编辑：这是我让它起作用的版本，以ffriend的被接受的答案为基础。

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 results = allPossibleCases(allArrays);
 //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]

- Yahel

16个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- adiga · Answer 1

你可以创建一个二维数组并使用reduce对其进行操作。然后使用flatMap在累加器数组和当前迭代的数组中创建字符串组合并将它们连接起来。

const data = [ ['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j'] ]

const output = data.reduce((acc, cur) => acc.flatMap(c => cur.map(n => c + n)) )

console.log(output)

- trincot · Answer 2

一个不使用递归的解决方案，同时包括一个通过其ID检索单个组合的函数：

function getCombination(data, i) {
    return data.map(group => {
        let choice = group[i % group.length]
        i = (i / group.length) | 0;
        return choice;
    });
}

function* combinations(data) {
    let count = data.reduce((sum, {length}) => sum * length, 1);
    for (let i = 0; i < count; i++) {
        yield getCombination(data, i);
    }
}

let data = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']];

for (let combination of combinations(data)) {
    console.log(...combination);
}

- Klortho · Answer 3

这是一个从上面几个答案中改编的版本，它按照 OP 中指定的顺序产生结果，并返回字符串而不是数组：

function *cartesianProduct(...arrays) {
  if (!arrays.length) yield [];
  else {
    const [tail, ...head] = arrays.reverse();
    const beginning = cartesianProduct(...head.reverse());
    for (let b of beginning) for (let t of tail) yield b + t;
  }
}

const first = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third =  ['f', 'g', 'h', 'i', 'j'];
console.log([...cartesianProduct(first, second, third)])

- Renato Echevarria · Answer 4

你也可以使用这个函数：

const result = (arrayOfArrays) => arrayOfArrays.reduce((t, i) => { let ac = []; for (const ti of t) { for (const ii of i) { ac.push(ti + '/' + ii) } } return ac })

result([['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']])
// which will output [ 'a/e/f', 'a/e/g', 'a/e/h','a/e/i','a/e/j','b/e/f','b/e/g','b/e/h','b/e/i','b/e/j','c/e/f','c/e/g','c/e/h','c/e/i','c/e/j','d/e/f','d/e/g','d/e/h','d/e/i','d/e/j']

当然，您可以在ac.push(ti + '/' + ii)中删除+ '/'以从最终结果中消除斜杠。并且您可以将那些for (... of ...)替换为forEach函数（加上相应的分号return ac之前），无论您更喜欢哪种方式。

- Tom Banister · Answer 5

一种不使用递归的数组方法：

const combinations = [['1', '2', '3'], ['4', '5', '6'], ['7', '8']];
let outputCombinations = combinations[0]

combinations.slice(1).forEach(row => {
  outputCombinations = outputCombinations.reduce((acc, existing) =>
    acc.concat(row.map(item => existing + item))
  , []);
});

console.log(outputCombinations);

- Dhaval · Answer 6

let arr1 = [`a`, `b`, `c`];
let arr2 = [`p`, `q`, `r`];
let arr3 = [`x`, `y`, `z`];
let result = [];

arr1.forEach(e1 => {
    arr2.forEach(e2 => {
        arr3.forEach(e3 => {
            result[result.length] = e1 + e2 + e3;
        });
    });
});


console.log(result);
/*
output:
[
  'apx', 'apy', 'apz', 'aqx',
  'aqy', 'aqz', 'arx', 'ary',
  'arz', 'bpx', 'bpy', 'bpz',
  'bqx', 'bqy', 'bqz', 'brx',
  'bry', 'brz', 'cpx', 'cpy',
  'cpz', 'cqx', 'cqy', 'cqz',
  'crx', 'cry', 'crz'
]
*/