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

Finding All Combinations (Cartesian product) of JavaScript array values

提问by Yahel

How can I produce all of the combinations of the values in N number of JavaScript arrays of variable lengths?

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

Let's say I have N number of JavaScript arrays, e.g.

假设我有 N 个 JavaScript 数组，例如

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

(Three arrays in this example, but its N number of arrays for the problem.)

（此示例中为三个数组，但问题的数组数为 N。）

And I want to output all the combinations of their values, to produce

我想输出它们值的所有组合，以产生

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

---

---

EDIT: Here's the version I got working, using ffriend's accepted answer as the basis.

编辑：这是我工作的版本，使用 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 r=allPossibleCases(allArrays);
 //outputs ["acd", "bcd", "azd", "bzd", "ace", "bce", "aze", "bze", "acf", "bcf", "azf", "bzf"]

回答by ffriend

This is not permutations, see permutations definitionsfrom Wikipedia.

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

But you can achieve this with 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;
  }

}

You can also make it with loops, but it will be a bit tricky and will require implementing your own analogue of stack.

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

回答by le_m

I suggest a simple recursive generator functionas follows:

我建议一个简单的递归生成器函数如下：

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

回答by David Tang

You don't need recursion, or heavily nested loops, or even to generate/store the whole array of permutations in memory.

您不需要递归或大量嵌套的循环，甚至不需要在内存中生成/存储整个排列数组。

Since the number of permutations is the product of the lengths of each of the arrays (call this numPerms), you can create a function getPermutation(n)that returns a unique permutation between index 0and numPerms - 1by calculating the indices it needs to retrieve its characters from, based on n.

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

How is this done? If you think of creating permutations on arrays each containing: [0, 1, 2, ... 9] it's very simple... the 245th permutation (n=245) is "245", rather intuitively, or:

这是怎么做的？如果您想在每个包含 [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]

The complication in your problem is that array sizes differ. We can work around this by replacing the n/100, n/10, etc... with other divisors. We can easily pre-calculate an array of divisors for this purpose. In the above example, the divisor of 100 was equal to arrayTens.length * arrayOnes.length. Therefore we can calculate the divisor for a given array to be the product of the lengths of the remaining arrays. The very last array always has a divisor of 1. Also, instead of modding by 10, we mod by the length of the current array.

您问题的复杂性在于数组大小不同。我们可以通过更换解决此n/100，n/10与其它约数，等等。为此，我们可以轻松地预先计算一组除数。在上面的例子中，100 的除数等于arrayTens.length * arrayOnes.length。因此，我们可以将给定数组的除数计算为剩余数组长度的乘积。最后一个数组的除数总是 1。此外，我们不是以 10 为单位，而是以当前数组的长度为单位。

Example code is below:

示例代码如下：

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

回答by sectus

Provided answers looks too difficult for me. So my solution is:

提供的答案对我来说太难了。所以我的解决方案是：

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

回答by Oriol

You can use a typical backtracking:

您可以使用典型的回溯：

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

I used generator functions to avoid allocating all the results simultaneously, but if you want you can

我使用生成器函数来避免同时分配所有结果，但如果你愿意，你可以

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

回答by Vikas Gautam

Copy of le_m's Answer to take Array of Arrays directly:

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

Hope it saves someone's time.

希望它可以节省某人的时间。

回答by Nina Scholz

You could take a single line approach by generating a cartesian product.

您可以通过生成笛卡尔积来采用单行方法。

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

回答by kathir

Easiest way to find the Combinations

找到组合的最简单方法

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

回答by adiga

You could create a 2D array and reduceit. Then use flatMapto create combinations of strings in the accumulator array and the current array being iterated and concatenate them.

你可以创建一个二维数组和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)

回答by Marthijn Bontekoning

If you're looking for a flow-compatible function that can handle two dimensional arrays with any item type, you can use the function below.

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

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

out:

出去：

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