From array, generate all distinct, non-empty subarrays, with preserved order

Question

I have an array, with subarrays and need an algorithm that generates all possible distinct combinations of the subarrays. The resultant combinations can be any length. For example, if the Array has 4 subarrays, the first subarray by itself would be a unique and valid resultant combination, as would any other unique combination of any length.

A combination with the sub-array with the same items in a different order would not be considered unique.

let mainArray = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]]

// Valid resultant combinations:
[[0.3, 1]]
[[0.3, 1], [0.5, 2]]
[[0.3, 1], [0.5, 2], [0.6, 3]]
[[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]]
[[0.5, 2]]
[[0.5, 2], [0.6, 3]]
[[0.5, 2], [0.6, 3], [0.3, 4]]
[[0.6, 3]]
[[0.6, 3], [0.3, 4]]
[[0.3, 4]]
[[0.3, 1], [0.6, 3], [0.3, 4]]
[[0.3, 1], [0.5, 2], [0.3, 4]]
[[0.3, 1], [0.3, 4]]
[[0.3, 1], [0.6, 3]]
[[0.5, 2], [0.3, 4]]

// Don’t think I missed any.

I tried writing a manual process with 4 nested sub-loops, incrementing the item that was skipped in various ways and it has gotten unruly. I don't believe it is actually functioning as intended, so I am hoping someone who has a better knowledge of Set math and Javascript could assist. — Tim Nickels, Feb 19 '20 at 15:56
If you don’t need to preserve order, i.e. allow `[ [ 0.5, 2 ], [ 0.3, 1 ] ]` and `[ [ 0.3, 4 ], [ 0.5, 2 ], [ 0.3, 1 ] ]` as well, see [All Array Combination in JavaScript](/q/56649241/4642212). — Sebastian Simon, Sep 23 '21 at 20:58

score 2 · Accepted Answer · answered Feb 19 '20 at 16:18

For a more convenient handling, you could take an array of indices and write the code for getting all combinations.

Later, you could replace the array with indices by the real values.

This approach works with a recusion which keeps an array of collected items and an index, which points to the handed over array.

At start, you have a standard exit condition of a recusion which checks if the index is greater than possible and adds the collected values to the result set.

The following part calls the function again with the peviously collected value and a new value from the array and an incremented index and with aother call with only a changed index (here, the actual item is not used).

function getCombinations(array) {
    function iter(temp, index) {
        if (index >= array.length) {
            result.push(temp);
            return;
        }

        iter([...temp, array[index]], index + 1);
        iter(temp, index + 1);
    }
    
    var result = [];
    iter([], 0);
    return result;
}

let array = [[0.3, 1], [0.5, 2], [0.6, 3], [0.3, 4]];

console.log('indices')
getCombinations([...array.keys()]).forEach(a => console.log(...a));
console.log('arrays')
getCombinations(array).forEach(a => console.log(...a.map(b => JSON.stringify(b))));

.as-console-wrapper { max-height: 100% !important; top: 0; }

kanine · Answer 2 · 2020-02-20T17:10:15.030

The algorithm would be based on the following logic. How many total possible sub-arrays exist? I. Let us consider there is only one item: ( _ ) So first sub array -> I don't pick the item. Second array -> I pick the item. Which means two sub arrays. II. Let us consider there are two items: ( _ ) ( _ ) So first sub array -> I don't pick the 1st item.I pick the 2nd item. Second array -> I pick the 1st item.I pick the 2nd item. So first sub array -> I don't pick the 2nd item.I don't pick the 1st item. Second array -> I pick the 2nd item.I pick the 1st item. Which means 4 sub arrays.

So I can generalise this, at each position, I can either pick it or not. Which means two values per position. So for n items -> 2x2x.....2 (n times) or 2ⁿ

So for three items, here's how we can work out a solution for three items :
    |Item1|Item2|Item3|     |Item1|Item2|Item3|
    ___________________     ___________________
    |  ✘  |  ✘  |  ✘  |  or |  0  |  0  |  0  |
    |  ✘  |  ✘  |  ✔  |  or |  0  |  0  |  1  |
    |  ✘  |  ✔  |  ✘  |  or |  0  |  1  |  0  |
    |  ✘  |  ✔  |  ✔  |  or |  0  |  1  |  1  |
    |  ✔  |  ✘  |  ✘  |  or |  1  |  0  |  0  |
    |  ✔  |  ✘  |  ✔  |  or |  1  |  0  |  1  |
    |  ✔  |  ✔  |  ✘  |  or |  1  |  1  |  0  |
    |  ✔  |  ✔  |  ✔  |  or |  1  |  1  |  1  | 
So if we run from 0 to (2ⁿ - 1), convert to binary and see show the only item which matches the ones, and not the zeros.
The pseudocode would be something like this:
 n -> list.length dummyList -> [] for i:0 to 2^n-1
    dummy2 -> []
    toBinary -> binary(i)
    for j: 0 to n-1
        if toBinary[j] equals 1
           insert list[j] to dummy2
    insert dummy2 to dummyList 
Time complexity = n x 2ⁿ

function allSubs(list){
    let len = list.length;
    let lenraisedtoTwo = 1<<len;
    let nwArr = Array(lenraisedtoTwo).fill().map((_,idx)=>list.filter(($,ind)=>idx.toString(2).padStart(len)[ind]==="1"))
    return nwArr
}
abc.innerText = JSON.stringify(allSubs([1,2,3]))

<div id="abc">This div contains the result for all possible combinations</div>

score 0 · Answer 3 · answered Feb 20 '20 at 15:26

Here's another approach:

function combinations(array) {
  const results = [];
  for (let item of array) {
    // take every result that is in the results yet, 
    const withItem = results.map(row => [...row, item]);
    // add that result + the current item
    results.push(...withItem);
    // also add just the current item
    results.push([item]);
  }
  return results;
}

or like this:

const values = [1,2,3,4];

function combinations(array) {
  return array.reduce((results, item) => [...results, ...results.map(row => [...row, item]), [item]], []);
}

console.log(combinations(values).join("\n"));

.as-console-wrapper{top:0;max-height:100%!important}

From array, generate all distinct, non-empty subarrays, with preserved order

3 Answers3

Linked

Related