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

Question

请注意:链接的问题“如何为两个数组的内容创建所有可能的组合？” 没有解决这个特定问题。标记为不完全理解这种特定排列和要求的人。

如果您有两个数组(arr1、arr2)，每个数组中有 n 个元素(即每个数组的长度相同)，那么问题是:在元素与相同数组中的其他元素不匹配且顺序无关紧要的情况下，获取/确定所有可能匹配项的最佳方法是什么？

例如，假设我有:

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

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