Best way to generate all unique combinations of an array?

user_1830262 0
Viewed 781

Assume I have this array:

const input = [“a”, “b”, “c”, “d”];

I want to create this output:

[
  [“a”],
  [“a”, “b”],
  [“a”, “c”],
  [“a”, “d”],
  [“a”, “b”, “c”],
  [“a”, “b”, “d”],
  [“a”, “c”, “d”],
  [“a”, “b”, “c”, “d”],
  [“b”],
  [“b”, “c”],
  [“b”, “d”],
  [“b”, “c”, “d”],
  [“c”],
  [“c”, “d”],
  [“d”]
]

I don’t care about the order, or the length of the combos, just need all the various ways to uniquely combine the items in the array.

What is the best way to do this in JavaScript? I suspect there’s a beautiful recursive solution, but iterative would work too.

Also, what is the correct technical term for this?

recursion arrays javascript
2 Answers

The correct technical term is power set. Here is the canonical recursive form:

const f = (A, i=0) => i == A.length ? [[]] : f(A, i+1).flatMap(x => [x, [A[i]].concat(x)]);

console.log(JSON.stringify(f(['a', 'b', 'c', 'd'])));

user_20347870

Recursive solution probably is the easiest to understand, although I guess there are other more efficient (in terms of computation complexity) solutions too.

First of all, the actual elements in the array do not matter, so that we can just use their indexes (0...n-1) to do the computation, later we convert those indexes into actual elements by actualArray = indexArray.map(i => inputArray[i]). In the discussion below, we assume indexes are stored in the output/result.

Then, since the order in the combination does not matter, and since everything (the index) within the combination must be unique, we can just make sure the indexes in the combinations are always in increasing order.

So, we can start with the combinations (array of arrays) that contain only 1 elements. Without any computation we all know those are: [[0], [1], [2], [3], ... [n-1]]. We can write code to generate them and use them as the seeds.

Then, for finding out all combinations (array of arrays) containing m+1 elements based on already known combinations (array of arrays) containing m elements, we can do this:

  1. Iterate through all combinations having m elements (array of arrays)
    1. For each combination (array of length m),
      1. Iterate through the range between (inclusive at both ends) combination[combination.length -1] and n - 1 if the range is valid for finding the next index
        1. Make a copy of the original array and append the new index to it. Such as newCombination = [...combination, newIndex]. This is a new combination containing m+1 elements.
        2. Add the newly found combination to the result.
  2. Now we have found all combinations having m+1 elements. They can be used to find all combinations having m+2 elements.

We can do this until we find the last combination, which contains n elements.

To facilitate the algorithm described above, the internal data structure could be:

[
   [[0], [1], [2], ..., [n-1]],   // indexes of combinations with 1 elements
   [[0, 1], [0, 2], ..., [n-2, n-1]],  // indexes of combinations with 2 elements
   ...
   [[0, 2, ... n-1]],        // indexes of combinations with n elements
]

To verify the correctness, we just need to check these:

  • Total number of combinations is the same as what we can calculate by math
  • Within each of the combinations, elements are always in increasing order
  • There's no duplicated combinations (adding combination.join(',') to a Set could be handy)

BTW, this is just my thoughts, I have not verified it with any real code or data :-)

user_141304710
Related