4

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?

jkhoffman
  • 199
  • 2
  • 11
  • Permutations is the word you are looking for. Bruteforce too. – Cid Oct 23 '20 at 23:06
  • 1
    No, these aren't permutations. Combinations is the correct term here. – ggorlen Oct 23 '20 at 23:12
  • I agree with @Cid https://en.wikipedia.org/wiki/Permutation as the output respects the element order. --- _"combination is a selection of items from a collection, such that the order of selection does not matter (unlike permutations)."_ Or does that not matter? – evolutionxbox Oct 23 '20 at 23:14
  • The target output looks like a binary count. `1000` would be `['a']`, and `1111` would be `['a','b','c','d']` – evolutionxbox Oct 23 '20 at 23:16
  • 1
    Sorry, I don't see any ordering going on here. Permutations deal with order, combinations deal with grouping. This isn't a cartesian product, either since we're dealing with one list. OP wants the JS version of Python's `[list(itertools.combinations("abcd", i)) for i in range(1, 5)]` but flattened. Should be a clear dupe somewhere but I can never seem to find dupes in this category because of these same terminology mix-ups. – ggorlen Oct 23 '20 at 23:18
  • 2
    Does this answer your question? [Find all possible subset combos in an array?](https://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array) – Nick Oct 23 '20 at 23:30
  • This can be generated using a reversed binary count from 1 to 16. – evolutionxbox Oct 23 '20 at 23:30
  • 1
    @ggorlen found one. just needs to change the filtering based on a min length of 2 to a min length of 1. I especially like zovio answer to that question – Nick Oct 23 '20 at 23:31
  • 1
    Nicely done. There should be a dupe finder badge for this. – ggorlen Oct 23 '20 at 23:35

2 Answers2

6

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'])));
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
  • Or similarly, `const powerSet = ([x, ...xs]) => x == undefined ? [[]] : powerSet (xs) .flatMap (p => [p, [x, ...p]])` – Scott Sauyet Oct 24 '20 at 16:51
  • @ScottSauyet that would make unnecessary copies of the original array. – גלעד ברקן Oct 24 '20 at 16:56
  • Yes, there are trade-offs for everything. Mine sacrifices some performance for a more elegant implementation. Yours sacrifices the ability to call it in certain ways (think `[set1, set2, set3].map(f)`) for the convenience of default parameters. Options are good. – Scott Sauyet Oct 25 '20 at 00:35
  • @ScottSauyet oh right, you and I have discussed the default parameters and `map` before. I guess for that, we would need a wrapper for this. – גלעד ברקן Oct 25 '20 at 00:37
2

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 :-)

James Hu
  • 21
  • 2