使用JavaScript将两个数组的所有可能组合作为一个数组获取 [英] Get all possible set of combinations of two arrays as an array of arrays with JavaScript

问题描述

请注意:链接的问题:如何为两个数组的内容创建每种可能的组合?" 不能 解决此特定问题.标记者并不完全了解此特定排列和要求.

如果您有两个数组( arr1 ， arr2 )，每个数组中有n个元素(即每个数组的长度相同)，那么问题是:获取/确定所有可能匹配项的最佳方法是什么?当元素与 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"]] 

我正在尝试使用香草JavaScript进行此操作，但也完全愿意使用 Lodash .要获得额外的好处，因为这可能会失控，因此速度和性能很重要.但是现在，我只是想得到一些可以产生适当结果集的东西.为了限制这一点，此函数可能不能与两个以上的每个包含50个元素的数组一起使用.

这是我最近的尝试(使用lodash):

 函数getMatches(arr1，arr2){var matchs = [];for(var arr1i = 0，arr1l = arr1.length; arr1i< arr1l; arr1i ++){for(var arr2i = 0，arr2l = arr2.length; arr2i< arr2l; arr2i ++){matchs.push(_(arr1).zip(arr2).value());arr2.push(arr2.shift());}}返回比赛；} 

解决方案

[[A，1]，[B，2]]

与

相同

[[B，2]，[A，1]]

在您的情况下为

，这意味着解决方案取决于您与数组的第一个元素配对的对象.您可以将n个不同的元素作为第二个元素与第一个元素配对，然后将n-1个不同的元素作为第二个元素与第二个元素配对，依此类推，所以您就有n个！可能性，即可能的排列数量.

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

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

  const排列=函数*(元素){如果(elements.length === 1){产量要素;} 别的 {让[first，... rest] =元素；for(让perm of permutations(rest)排列){for(让i = 0; i< elements.length; i ++){让开始= perm.slice(0，i);让休息= perm.slice(i);产生[...开始，首先，...休息]；}}}}var other = ['A'，'B'，'C'];var myPermutations =排列(['X'，'Y'，'Z']);var done = false;而(！完成){var next = myPermutations.next();如果(！(done = next.done)){var输出= [];for(var i = 0; i< next.value.length; i ++)output.push([other [i]，next.value [i]]);console.log(输出);}} 

Please note: the linked question, "How can I create every combination possible for the contents of two arrays?" does not solve this particular question. The persons that labeled that did not fully understand this specific permutation and request.

If you have two arrays (arr1, arr2) with n elements in each array (i.e., each array will be the same length), then the question is: What's the best method to get/determine all the possible matches where elements do not match with other elements in the same array and where order does not matter?

For example, let's say I have:

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

I would like to get back an array of arrays where each element of one array is paired with an element of another array. So the result would be a unique set of arrays:

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

Please note, these two arrays would be the same:

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

I am trying to do this with vanilla JavaScript but am completely open to using Lodash as well. For an added bonus, since this can get out of control, speed and performance are important. But right now, I am just trying to get something that would yield a proper result set. To limit this, this function would probably not be used with more than two arrays of 50 elements each.

Here is my latest attempt (using 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;
}

解决方案

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

is the same as

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

in your case, which means that the solution depends on what you pair to the first elements of your array. You can pair n different elements as second elements to the first one, then n - 1 different elements as second elements to the second one and so on, so you have n! possibilities, which is the number of possible permutations.

So, if you change the order of the array elements but they are the same pair, they are equivalent, so you could view the first elements as a fixed ordered set of items and the second elements as the items to permutate.

Having arr1 = [a1, ..., an] and arr2 = [b1, ..., bn] we can avoid changing the order of a1. So, you permutate the inner elements and treat the outer elements' order as invariant, like:

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

这篇关于使用JavaScript将两个数组的所有可能组合作为一个数组获取的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！