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

Question

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

Answer 1

这不是排列组合，参见维基百科的排列组合定义。

但您可以通过递归实现：

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

}

console.log(allPossibleCases(allArrays))

你也可以用循环来实现，但这会有点棘手，并需要实现自己的堆栈模拟器。

- ffriend

Answer 2

我建议使用以下简单的递归生成器函数：

// Generate cartesian product of given iterables:
function* cartesian(head, ...tail) {
  let remainder = tail.length ? cartesian(...tail) : [[]];
  for (let r of remainder) for (let h of head) yield [h, ...r];
}

// Example:
const first  = ['a', 'b', 'c', 'd'];
const second = ['e'];
const third  = ['f', 'g', 'h', 'i', 'j'];

console.log(...cartesian(first, second, third));

- le_m

---

这确实很美。对于那些想要使用未知数量的输入并将结果存储在数组中的人，可以这样做：const product = [...cartesian.apply(this, [first, second, third, fourth, etc])]; - Andrew

@Andrew 为什么不使用展开运算符将参数放入笛卡尔积函数中，而是使用.apply? const product = [...cartesian(...unknownNumberOfInputs)]; - Sukima

很好。如何修改以满足此版本，其中需要单个、双倍等字符串的排列组合。 - mplungjan

Answer 3

无需使用递归、嵌套循环或在内存中生成/存储所有排列的数组。

由于排列数量是每个数组长度的乘积（称之为numPerms），因此您可以创建一个名为getPermutation(n)的函数，它根据n计算出需要检索字符的索引以返回介于索引0和numPerms-1之间的唯一排列。

如何实现呢？如果您想在包含[0, 1, 2, ... 9]的数组上创建排列，那么很简单...第245个排列（n = 245）是"245"，这相当直观，或者：

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

在您的问题中复杂的部分是数组大小不同。我们可以通过替换n / 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;
}

- David Tang

---

非常好。不过这里有个拼写错误，results 应该显示为 result -- 我注意到你在计算除数时倒序循环，我假设数组中除数的位置很重要？ - Gary Green

@Gary，感谢你注意到了这个问题。除数的顺序很重要，因为第一个除数依赖于第二个，第二个依赖于第三个，以此类推...所以通过倒序循环，我可以更轻松地构建它。 - David Tang

@Box9：这个函数能用于一个数组吗？难道不应该是（n*n）-（n-1）吗？ - Micromega

如果它适用于1个数组，并且结果（n * n）-（n-1）可以用来制作成本矩阵吗？例如，对于旅行商问题？ - Micromega

不是排列，如上所述，而是组合。你不应该更新你的答案并将排列替换为组合吗？算法本身很棒。 - Zane

Answer 4

提供的答案对我来说太难了。因此，我的解决方案是:

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

- sectus

---

你好。如何修改代码以返回一个二维数组而不是字符串数组？所以，将 ["acd", "ace", "acf" ...] 改为 [["a","c","d"], ["a","c","e"] ....]。 - Thomas

Answer 5

你可以通过生成笛卡尔积的方式采用单行方法。

result = items.reduce(
    (a, b) => a.reduce(
        (r, v) => r.concat(b.map(w => [].concat(v, w))),
        []
    )
);

var items = [['a', 'b', 'c', 'd'], ['e'], ['f', 'g', 'h', 'i', 'j']],
    result = items.reduce((a, b) => a.reduce((r, v) => r.concat(b.map(w => [].concat(v, w))), []));
 
console.log(result.map(a => a.join(' ')));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

如何使用来回答此问题。 - mplungjan

Answer 6

复制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];
}

希望能为某些人节省时间。

- Vikas Gautam

---

你可以这样使用le_m的方法：cartesian(...arrOfArr)。 - DarkNeuron

Answer 7

找到组合的最简单方法

const arr1= [ 'a', 'b', 'c', 'd' ];
const arr2= [ '1', '2', '3' ];
const arr3= [ 'x', 'y', ];

const all = [arr1, arr2, arr3];

const output = all.reduce((acc, cu) => { 
    let ret = [];
      acc.map(obj => {
        cu.map(obj_1 => {
          ret.push(obj + '-' + obj_1) 
        });
      });
      return ret;
   })

console.log(output);

- kathir

---

这在一个空数组上失败。 - Bergi

Answer 8

您可以使用典型的回溯法：

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"]

- Oriol

Answer 9

如果您正在寻找一种可以处理任何条目类型的二维数组的流兼容函数，可以使用下面的函数。

const getUniqueCombinations = <T>(items : Array<Array<T>>, prepend : Array<T> = []) : Array<Array<T>> => {
    if(!items || items.length === 0) return [prepend];

    let out = [];

    for(let i = 0; i < items[0].length; i++){
        out = [...out, ...getUniqueCombinations(items.slice(1), [...prepend, items[0][i]])];
    }

    return out;
}

A visualisation of the operation:

in:

[
    [Obj1, Obj2, Obj3],
    [Obj4, Obj5],
    [Obj6, Obj7]
]

输出：

[
    [Obj1, Obj4, Obj6 ],
    [Obj1, Obj4, Obj7 ],
    [Obj1, Obj5, Obj6 ],
    [Obj1, Obj5, Obj7 ],
    [Obj2, Obj4, Obj6 ],
    [Obj2, Obj4, Obj7 ],
    [Obj2, Obj5, Obj6 ],
    [Obj2, Obj5, Obj7 ],
    [Obj3, Obj4, Obj6 ],
    [Obj3, Obj4, Obj7 ],
    [Obj3, Obj5, Obj6 ],
    [Obj3, Obj5, Obj7 ]
]

- Marthijn Bontekoning

Answer 10

大卫·唐（David Tang）2021年版的答案，受到尼尔·蒙福德（Neil Mountford）的答案启发。

const getAllCombinations = (arraysToCombine) => {
  const divisors = [];
  let permsCount = 1;
  for (let i = arraysToCombine.length - 1; i >= 0; i--) {
      divisors[i] = divisors[i + 1] ? divisors[i + 1] * arraysToCombine[i + 1].length : 1;
      permsCount *= (arraysToCombine[i].length || 1);
  }

  const getCombination = (n, arrays, divisors) => arrays.reduce((acc, arr, i) => {
      acc.push(arr[Math.floor(n / divisors[i]) % arr.length]);
      return acc;
  }, []);

  const combinations = [];
  for (let i = 0; i < permsCount; i++) {
      combinations.push(getCombination(i, arraysToCombine, divisors));
  }
  return combinations;
};

console.log(getAllCombinations([['a', 'b'], ['c', 'z'], ['d', 'e', 'f']]));

基准测试：https://jsbench.me/gdkmxhm36d/1

- Georgiy Bukharov