获取两个数组的所有可能组合集作为数组的数组 JavaScript

Question

请注意：链接的问题 "How can I create every combination possible for the contents of two arrays?" 没有解决这个特定问题。标记为不完全理解这种特定排列和要求的人。

如果您有两个数组 (arr1, arr2)，每个数组中有 n 个元素（即每个数组的长度相同），那么问题是：最好的方法是什么get/determine 所有可能的匹配项，其中元素与 same 数组中的其他元素不匹配且顺序无关紧要？

例如，假设我有：

arr1 = ["A","B","C"];
arr2 = ["Z","Y","X"];

我想取回一个数组数组，其中一个数组的每个元素都与另一个数组的元素配对。所以结果将是一组独特的数组：

matches = [
    [["A","Z"],["B","Y"],["C","X"]],
    [["A","Z"],["B","X"],["C","Y"]],
    [["A","Y"],["B","X"],["C","Z"]],
    [["A","Y"],["B","Z"],["C","X"]],
    [["A","X"],["B","Z"],["C","Y"]],
    [["A","X"],["B","Y"],["C","Z"]],
]

请注意，这两个数组是相同的：

[["A","Z"],["B","Y"],["C","X"]]
[["B","Y"],["C","X"],["A","Z"]]

我正在尝试使用 vanilla JavaScript 来做到这一点，但我也完全愿意使用 Lodash。为了获得额外的好处，因为这可能会失控，所以速度和性能很重要。但是现在，我只是想获得能够产生正确结果集的东西。为了限制这一点，此函数可能不会用于两个以上的数组，每个数组包含 50 个元素。

这是我最近的尝试（使用 lodash）：

function getMatches(arr1, arr2){
    var matches = [];
    for (var arr1i = 0, arr1l = arr1.length; arr1i < arr1l; arr1i++) {
        for (var arr2i = 0, arr2l = arr2.length; arr2i < arr2l; arr2i++) {
            matches.push(_(arr1).zip(arr2).value());
            arr2.push(arr2.shift());
        }
    }
    return matches;
}

Answer 1

您正在寻找 permutations。你的元组的第一个元素总是相同的，第二个元素被置换，这样你就可以获得所有不同的组合集。

const arr1 = ["A","B","C"];
const arr2 = ["Z","Y","X"];

const result = permutate(arr2).map(permutation =>
    permutation.map((el, i) => [arr1[i], el])
);

Answer 2

[[A, 1], [B, 2]]

与

相同

[[B, 2], [A, 1]]

在您的情况下，这意味着解决方案取决于您将什么与数组的第一个元素配对。您可以将 n 个不同的元素作为第二个元素与第一个元素配对，然后将 n - 1 个不同的元素作为第二个元素与第二个元素配对，依此类推，所以您有 n!可能性，这是可能的排列数。

因此，如果您更改数组元素的顺序但它们是同一对，则它们是等价的，因此您可以将第一个元素视为一组固定有序的项目，将第二个元素视为要置换的项目.

有了 arr1 = [a1, ..., an] 和 arr2 = [b1, ..., bn] 我们可以避免改变 a1 的顺序。因此，您排列内部元素并将外部元素的顺序视为不变的，例如：

const permutations = function*(elements) {
  if (elements.length === 1) {
    yield elements;
  } else {
    let [first, ...rest] = elements;
    for (let perm of permutations(rest)) {
      for (let i = 0; i < elements.length; i++) {
        let start = perm.slice(0, i);
        let rest = perm.slice(i);
        yield [...start, first, ...rest];
      }
    }
  }
}

var other = ['A', 'B', 'C'];
var myPermutations = permutations(['X', 'Y', 'Z']);
var done = false;
while (!done) {
    var next = myPermutations.next();
    if (!(done = next.done)) {
        var output = [];
        for (var i = 0; i < next.value.length; i++) output.push([other[i], next.value[i]]);
        console.log(output);
    }
}

Answer 3

此实现使用 Typescript 和 Lodash。

const permutations = <T>(arr: T[]): T[][] => {
  if (arr.length <= 2)
    return arr.length === 2 ? [arr, [arr[1], arr[0]]] : [arr];
  return reduce(
    arr,
    (acc, val, i) =>
      concat(
        acc,
        map(
          permutations([...slice(arr, 0, i), ...slice(arr, i + 1, arr.length)]),
          vals => [val, ...vals]
        )
      ),
    [] as T[][]
  );
};

获取两个数组的所有可能组合集作为数组的数组 JavaScript

Get all possible set of combinations of two arrays as an array of arrays with JavaScript

javascript

arrays

combinations

combinatorics

lodash