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

Question

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

How is this a duplicate? And where is the original question being asked? The linked question, "How can I create every combination possible for the contents of two arrays?" does not solve this particular question. Let me re-title as I am not interested in paired combinations per se but the set of combinations. — Travis Smith, Sep 05 '19 at 14:47

score 2 · Accepted Answer · answered Sep 05 '19 at 17:42

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

score 0 · Answer 2 · answered Sep 05 '19 at 16:04

0

You're just looking for permutations. The first elements of your tuples are always the same, the second ones are permuted so that you get all distinct sets of combinations.

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

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

answered Sep 05 '19 at 16:04

Bergi

630,263
148
957
1,375

Could you add the function you are calling in a snippet? – mplungjan Jul 31 '20 at 11:01
@mplungjan Any of the functions in the linked canonical should work – Bergi Jul 31 '20 at 13:08
But the link you gave is not pointing at the one you wanted – mplungjan Jul 31 '20 at 13:13
@mplungjan I linked the question, not a specific implementation. The one from [this answer](https://stackoverflow.com/a/37580979/1048572) would work fine, for example, but it's up the OP to decide which one to use (they might output the permutations in different orders). – Bergi Jul 31 '20 at 20:57

score 0 · Answer 3 · answered May 14 '22 at 09:44

This implementation uses Typescript and 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[][]
  );
};

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

3 Answers3

Linked

Related