0

UPDATE: I totally underestimated the magnitude of the problem. It's impossible to compute, at least in 2018 and the foreseeable future!

Given

SET = ['a', 'b', 'c', 'd', 'e', 'f', 'g']

And

SUBSET_SIZES = [3, 2, 2]

I want to find all possible grouping/subset combinations of SET, as determined by SUBSET_SIZES, while using up all of the items in the original set.

The result for the above input would look like this:

[['a', 'b', 'c'], ['d', 'e'], ['f', 'g']],
[['a', 'b', 'c'], ['d', 'f'], ['e', 'g']],
[['a', 'b', 'c'], ['d', 'g'], ['e', 'f']],
[['a', 'b', 'c'], ['e', 'f'], ['d', 'g']],
[['a', 'b', 'c'], ['e', 'g'], ['d', 'f']],
[['a', 'b', 'c'], ['f', 'g'], ['d', 'e']],
[['a', 'b', 'd'], ['c', 'e'], ['f', 'g']],
[['a', 'b', 'd'], ['c', 'f'], ['e', 'g']],
[['a', 'b', 'd'], ['c', 'g'], ['e', 'f']],
[['a', 'b', 'd'], ['e', 'f'], ['c', 'g']],
... and 200 more ...

My actual data set will be larger (~ 50 items) and the subset sizes will vary between 4 to 6 items each, so I'm looking for a fairly efficient way to find the combinations. However, I'm okay with it taking 2-3 minutes to complete with larger datasets.

I'd like to implement that in JavaScript, so if you already know of a JavaScript code that can do the job, that'd be amazing. If it's ES6 generator code, even better! I'm running out of Googling power.

Below is a code snippet with a couple of Jasmine tests:

function getPossibleGroupCombinations() {
  return [];
}

describe('getPossibleGroupCombinations', () => {
  it('works with a tiny set', () => {
    const possibleCombos = getPossibleGroupCombinations(['a', 'b', 'c'], [2, 1]);

    expect(possibleCombos).toEqual([
      [['a', 'b'], ['c']],
      [['a', 'c'], ['b']],
      [['b', 'c'], ['a']],
    ]);
  });
  
  it('works with a big set', () => {
    const possibleCombos = getPossibleGroupCombinations(
      ['a', 'b', 'c', 'd', 'e', 'f', 'g'],
      [3, 2, 2]
    );

    expect(possibleCombos).toEqual([
      [['a', 'b', 'c'], ['d', 'e'], ['f', 'g']],
      [['a', 'b', 'c'], ['d', 'f'], ['e', 'g']],
      [['a', 'b', 'c'], ['d', 'g'], ['e', 'f']],
      [['a', 'b', 'c'], ['e', 'f'], ['d', 'g']],
      [['a', 'b', 'c'], ['e', 'g'], ['d', 'f']],
      [['a', 'b', 'c'], ['f', 'g'], ['d', 'e']],
      [['a', 'b', 'd'], ['c', 'e'], ['f', 'g']],
      [['a', 'b', 'd'], ['c', 'f'], ['e', 'g']],
      [['a', 'b', 'd'], ['c', 'g'], ['e', 'f']],
      [['a', 'b', 'd'], ['e', 'f'], ['c', 'g']],
      [['a', 'b', 'd'], ['e', 'g'], ['c', 'f']],
      [['a', 'b', 'd'], ['f', 'g'], ['c', 'e']],
      [['a', 'b', 'e'], ['c', 'd'], ['f', 'g']],
      [['a', 'b', 'e'], ['c', 'f'], ['d', 'g']],
      [['a', 'b', 'e'], ['c', 'g'], ['d', 'f']],
      [['a', 'b', 'e'], ['d', 'f'], ['c', 'g']],
      [['a', 'b', 'e'], ['d', 'g'], ['c', 'f']],
      [['a', 'b', 'e'], ['f', 'g'], ['c', 'd']],
      [['a', 'b', 'f'], ['c', 'd'], ['e', 'g']],
      [['a', 'b', 'f'], ['c', 'e'], ['d', 'g']],
      [['a', 'b', 'f'], ['c', 'g'], ['d', 'e']],
      [['a', 'b', 'f'], ['d', 'e'], ['c', 'g']],
      [['a', 'b', 'f'], ['d', 'g'], ['c', 'e']],
      [['a', 'b', 'f'], ['e', 'g'], ['c', 'd']],
      [['a', 'b', 'g'], ['c', 'd'], ['e', 'f']],
      [['a', 'b', 'g'], ['c', 'e'], ['d', 'f']],
      [['a', 'b', 'g'], ['c', 'f'], ['d', 'e']],
      [['a', 'b', 'g'], ['d', 'e'], ['c', 'f']],
      [['a', 'b', 'g'], ['d', 'f'], ['c', 'e']],
      [['a', 'b', 'g'], ['e', 'f'], ['c', 'd']],
      [['a', 'c', 'd'], ['b', 'e'], ['f', 'g']],
      [['a', 'c', 'd'], ['b', 'f'], ['e', 'g']],
      [['a', 'c', 'd'], ['b', 'g'], ['e', 'f']],
      [['a', 'c', 'd'], ['e', 'f'], ['b', 'g']],
      [['a', 'c', 'd'], ['e', 'g'], ['b', 'f']],
      [['a', 'c', 'd'], ['f', 'g'], ['b', 'e']],
      [['a', 'c', 'e'], ['b', 'd'], ['f', 'g']],
      [['a', 'c', 'e'], ['b', 'f'], ['d', 'g']],
      [['a', 'c', 'e'], ['b', 'g'], ['d', 'f']],
      [['a', 'c', 'e'], ['d', 'f'], ['b', 'g']],
      [['a', 'c', 'e'], ['d', 'g'], ['b', 'f']],
      [['a', 'c', 'e'], ['f', 'g'], ['b', 'd']],
      [['a', 'c', 'f'], ['b', 'd'], ['e', 'g']],
      [['a', 'c', 'f'], ['b', 'e'], ['d', 'g']],
      [['a', 'c', 'f'], ['b', 'g'], ['d', 'e']],
      [['a', 'c', 'f'], ['d', 'e'], ['b', 'g']],
      [['a', 'c', 'f'], ['d', 'g'], ['b', 'e']],
      [['a', 'c', 'f'], ['e', 'g'], ['b', 'd']],
      [['a', 'c', 'g'], ['b', 'd'], ['e', 'f']],
      [['a', 'c', 'g'], ['b', 'e'], ['d', 'f']],
      [['a', 'c', 'g'], ['b', 'f'], ['d', 'e']],
      [['a', 'c', 'g'], ['d', 'e'], ['b', 'f']],
      [['a', 'c', 'g'], ['d', 'f'], ['b', 'e']],
      [['a', 'c', 'g'], ['e', 'f'], ['b', 'd']],
      [['a', 'd', 'e'], ['b', 'c'], ['f', 'g']],
      [['a', 'd', 'e'], ['b', 'f'], ['c', 'g']],
      [['a', 'd', 'e'], ['b', 'g'], ['c', 'f']],
      [['a', 'd', 'e'], ['c', 'f'], ['b', 'g']],
      [['a', 'd', 'e'], ['c', 'g'], ['b', 'f']],
      [['a', 'd', 'e'], ['f', 'g'], ['b', 'c']],
      [['a', 'd', 'f'], ['b', 'c'], ['e', 'g']],
      [['a', 'd', 'f'], ['b', 'e'], ['c', 'g']],
      [['a', 'd', 'f'], ['b', 'g'], ['c', 'e']],
      [['a', 'd', 'f'], ['c', 'e'], ['b', 'g']],
      [['a', 'd', 'f'], ['c', 'g'], ['b', 'e']],
      [['a', 'd', 'f'], ['e', 'g'], ['b', 'c']],
      [['a', 'd', 'g'], ['b', 'c'], ['e', 'f']],
      [['a', 'd', 'g'], ['b', 'e'], ['c', 'f']],
      [['a', 'd', 'g'], ['b', 'f'], ['c', 'e']],
      [['a', 'd', 'g'], ['c', 'e'], ['b', 'f']],
      [['a', 'd', 'g'], ['c', 'f'], ['b', 'e']],
      [['a', 'd', 'g'], ['e', 'f'], ['b', 'c']],
      [['a', 'e', 'f'], ['b', 'c'], ['d', 'g']],
      [['a', 'e', 'f'], ['b', 'd'], ['c', 'g']],
      [['a', 'e', 'f'], ['b', 'g'], ['c', 'd']],
      [['a', 'e', 'f'], ['c', 'd'], ['b', 'g']],
      [['a', 'e', 'f'], ['c', 'g'], ['b', 'd']],
      [['a', 'e', 'f'], ['d', 'g'], ['b', 'c']],
      [['a', 'e', 'g'], ['b', 'c'], ['d', 'f']],
      [['a', 'e', 'g'], ['b', 'd'], ['c', 'f']],
      [['a', 'e', 'g'], ['b', 'f'], ['c', 'd']],
      [['a', 'e', 'g'], ['c', 'd'], ['b', 'f']],
      [['a', 'e', 'g'], ['c', 'f'], ['b', 'd']],
      [['a', 'e', 'g'], ['d', 'f'], ['b', 'c']],
      [['a', 'f', 'g'], ['b', 'c'], ['d', 'e']],
      [['a', 'f', 'g'], ['b', 'd'], ['c', 'e']],
      [['a', 'f', 'g'], ['b', 'e'], ['c', 'd']],
      [['a', 'f', 'g'], ['c', 'd'], ['b', 'e']],
      [['a', 'f', 'g'], ['c', 'e'], ['b', 'd']],
      [['a', 'f', 'g'], ['d', 'e'], ['b', 'c']],
      [['b', 'c', 'd'], ['a', 'e'], ['f', 'g']],
      [['b', 'c', 'd'], ['a', 'f'], ['e', 'g']],
      [['b', 'c', 'd'], ['a', 'g'], ['e', 'f']],
      [['b', 'c', 'd'], ['e', 'f'], ['a', 'g']],
      [['b', 'c', 'd'], ['e', 'g'], ['a', 'f']],
      [['b', 'c', 'd'], ['f', 'g'], ['a', 'e']],
      [['b', 'c', 'e'], ['a', 'd'], ['f', 'g']],
      [['b', 'c', 'e'], ['a', 'f'], ['d', 'g']],
      [['b', 'c', 'e'], ['a', 'g'], ['d', 'f']],
      [['b', 'c', 'e'], ['d', 'f'], ['a', 'g']],
      [['b', 'c', 'e'], ['d', 'g'], ['a', 'f']],
      [['b', 'c', 'e'], ['f', 'g'], ['a', 'd']],
      [['b', 'c', 'f'], ['a', 'd'], ['e', 'g']],
      [['b', 'c', 'f'], ['a', 'e'], ['d', 'g']],
      [['b', 'c', 'f'], ['a', 'g'], ['d', 'e']],
      [['b', 'c', 'f'], ['d', 'e'], ['a', 'g']],
      [['b', 'c', 'f'], ['d', 'g'], ['a', 'e']],
      [['b', 'c', 'f'], ['e', 'g'], ['a', 'd']],
      [['b', 'c', 'g'], ['a', 'd'], ['e', 'f']],
      [['b', 'c', 'g'], ['a', 'e'], ['d', 'f']],
      [['b', 'c', 'g'], ['a', 'f'], ['d', 'e']],
      [['b', 'c', 'g'], ['d', 'e'], ['a', 'f']],
      [['b', 'c', 'g'], ['d', 'f'], ['a', 'e']],
      [['b', 'c', 'g'], ['e', 'f'], ['a', 'd']],
      [['b', 'd', 'e'], ['a', 'c'], ['f', 'g']],
      [['b', 'd', 'e'], ['a', 'f'], ['c', 'g']],
      [['b', 'd', 'e'], ['a', 'g'], ['c', 'f']],
      [['b', 'd', 'e'], ['c', 'f'], ['a', 'g']],
      [['b', 'd', 'e'], ['c', 'g'], ['a', 'f']],
      [['b', 'd', 'e'], ['f', 'g'], ['a', 'c']],
      [['b', 'd', 'f'], ['a', 'c'], ['e', 'g']],
      [['b', 'd', 'f'], ['a', 'e'], ['c', 'g']],
      [['b', 'd', 'f'], ['a', 'g'], ['c', 'e']],
      [['b', 'd', 'f'], ['c', 'e'], ['a', 'g']],
      [['b', 'd', 'f'], ['c', 'g'], ['a', 'e']],
      [['b', 'd', 'f'], ['e', 'g'], ['a', 'c']],
      [['b', 'd', 'g'], ['a', 'c'], ['e', 'f']],
      [['b', 'd', 'g'], ['a', 'e'], ['c', 'f']],
      [['b', 'd', 'g'], ['a', 'f'], ['c', 'e']],
      [['b', 'd', 'g'], ['c', 'e'], ['a', 'f']],
      [['b', 'd', 'g'], ['c', 'f'], ['a', 'e']],
      [['b', 'd', 'g'], ['e', 'f'], ['a', 'c']],
      [['b', 'e', 'f'], ['a', 'c'], ['d', 'g']],
      [['b', 'e', 'f'], ['a', 'd'], ['c', 'g']],
      [['b', 'e', 'f'], ['a', 'g'], ['c', 'd']],
      [['b', 'e', 'f'], ['c', 'd'], ['a', 'g']],
      [['b', 'e', 'f'], ['c', 'g'], ['a', 'd']],
      [['b', 'e', 'f'], ['d', 'g'], ['a', 'c']],
      [['b', 'e', 'g'], ['a', 'c'], ['d', 'f']],
      [['b', 'e', 'g'], ['a', 'd'], ['c', 'f']],
      [['b', 'e', 'g'], ['a', 'f'], ['c', 'd']],
      [['b', 'e', 'g'], ['c', 'd'], ['a', 'f']],
      [['b', 'e', 'g'], ['c', 'f'], ['a', 'd']],
      [['b', 'e', 'g'], ['d', 'f'], ['a', 'c']],
      [['b', 'f', 'g'], ['a', 'c'], ['d', 'e']],
      [['b', 'f', 'g'], ['a', 'd'], ['c', 'e']],
      [['b', 'f', 'g'], ['a', 'e'], ['c', 'd']],
      [['b', 'f', 'g'], ['c', 'd'], ['a', 'e']],
      [['b', 'f', 'g'], ['c', 'e'], ['a', 'd']],
      [['b', 'f', 'g'], ['d', 'e'], ['a', 'c']],
      [['c', 'd', 'e'], ['a', 'b'], ['f', 'g']],
      [['c', 'd', 'e'], ['a', 'f'], ['b', 'g']],
      [['c', 'd', 'e'], ['a', 'g'], ['b', 'f']],
      [['c', 'd', 'e'], ['b', 'f'], ['a', 'g']],
      [['c', 'd', 'e'], ['b', 'g'], ['a', 'f']],
      [['c', 'd', 'e'], ['f', 'g'], ['a', 'b']],
      [['c', 'd', 'f'], ['a', 'b'], ['e', 'g']],
      [['c', 'd', 'f'], ['a', 'e'], ['b', 'g']],
      [['c', 'd', 'f'], ['a', 'g'], ['b', 'e']],
      [['c', 'd', 'f'], ['b', 'e'], ['a', 'g']],
      [['c', 'd', 'f'], ['b', 'g'], ['a', 'e']],
      [['c', 'd', 'f'], ['e', 'g'], ['a', 'b']],
      [['c', 'd', 'g'], ['a', 'b'], ['e', 'f']],
      [['c', 'd', 'g'], ['a', 'e'], ['b', 'f']],
      [['c', 'd', 'g'], ['a', 'f'], ['b', 'e']],
      [['c', 'd', 'g'], ['b', 'e'], ['a', 'f']],
      [['c', 'd', 'g'], ['b', 'f'], ['a', 'e']],
      [['c', 'd', 'g'], ['e', 'f'], ['a', 'b']],
      [['c', 'e', 'f'], ['a', 'b'], ['d', 'g']],
      [['c', 'e', 'f'], ['a', 'd'], ['b', 'g']],
      [['c', 'e', 'f'], ['a', 'g'], ['b', 'd']],
      [['c', 'e', 'f'], ['b', 'd'], ['a', 'g']],
      [['c', 'e', 'f'], ['b', 'g'], ['a', 'd']],
      [['c', 'e', 'f'], ['d', 'g'], ['a', 'b']],
      [['c', 'e', 'g'], ['a', 'b'], ['d', 'f']],
      [['c', 'e', 'g'], ['a', 'd'], ['b', 'f']],
      [['c', 'e', 'g'], ['a', 'f'], ['b', 'd']],
      [['c', 'e', 'g'], ['b', 'd'], ['a', 'f']],
      [['c', 'e', 'g'], ['b', 'f'], ['a', 'd']],
      [['c', 'e', 'g'], ['d', 'f'], ['a', 'b']],
      [['c', 'f', 'g'], ['a', 'b'], ['d', 'e']],
      [['c', 'f', 'g'], ['a', 'd'], ['b', 'e']],
      [['c', 'f', 'g'], ['a', 'e'], ['b', 'd']],
      [['c', 'f', 'g'], ['b', 'd'], ['a', 'e']],
      [['c', 'f', 'g'], ['b', 'e'], ['a', 'd']],
      [['c', 'f', 'g'], ['d', 'e'], ['a', 'b']],
      [['d', 'e', 'f'], ['a', 'b'], ['c', 'g']],
      [['d', 'e', 'f'], ['a', 'c'], ['b', 'g']],
      [['d', 'e', 'f'], ['a', 'g'], ['b', 'c']],
      [['d', 'e', 'f'], ['b', 'c'], ['a', 'g']],
      [['d', 'e', 'f'], ['b', 'g'], ['a', 'c']],
      [['d', 'e', 'f'], ['c', 'g'], ['a', 'b']],
      [['d', 'e', 'g'], ['a', 'b'], ['c', 'f']],
      [['d', 'e', 'g'], ['a', 'c'], ['b', 'f']],
      [['d', 'e', 'g'], ['a', 'f'], ['b', 'c']],
      [['d', 'e', 'g'], ['b', 'c'], ['a', 'f']],
      [['d', 'e', 'g'], ['b', 'f'], ['a', 'c']],
      [['d', 'e', 'g'], ['c', 'f'], ['a', 'b']],
      [['d', 'f', 'g'], ['a', 'b'], ['c', 'e']],
      [['d', 'f', 'g'], ['a', 'c'], ['b', 'e']],
      [['d', 'f', 'g'], ['a', 'e'], ['b', 'c']],
      [['d', 'f', 'g'], ['b', 'c'], ['a', 'e']],
      [['d', 'f', 'g'], ['b', 'e'], ['a', 'c']],
      [['d', 'f', 'g'], ['c', 'e'], ['a', 'b']],
      [['e', 'f', 'g'], ['a', 'b'], ['c', 'd']],
      [['e', 'f', 'g'], ['a', 'c'], ['b', 'd']],
      [['e', 'f', 'g'], ['a', 'd'], ['b', 'c']],
      [['e', 'f', 'g'], ['b', 'c'], ['a', 'd']],
      [['e', 'f', 'g'], ['b', 'd'], ['a', 'c']],
      [['e', 'f', 'g'], ['c', 'd'], ['a', 'b']],
    ]);
  });
});


// load jasmine htmlReporter
(function() {
  var env = jasmine.getEnv();
  env.addReporter(new jasmine.HtmlReporter());
  env.execute();
}());
<link href="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.css" rel="stylesheet"/>
<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine.js"></script>
<script src="https://cdn.jsdelivr.net/jasmine/1.3.1/jasmine-html.js"></script>
Merott
  • 7,189
  • 6
  • 40
  • 52
  • 4
    I think you're underestimating the number of combinations you'll have. If you have 50 items and 10 subsets of size 5, for example, you end up with 49120458506088132224064306071170476903628800 possibilities. I don't think it's reasonable to expect enumerating that to complete in 2 or 3 aeons, never mind 2 or 3 minutes. (That's 50!/(5!**10), in case you're curious. I computed it with Python, because it has bignum support.) – rici Sep 26 '18 at 20:27
  • it's called permutation. the grouping is just cosmetically. jou could take this approach for getting the permuation one by one: https://stackoverflow.com/q/40441586/1447675 – Nina Scholz Sep 26 '18 at 21:06
  • @rici You're right. I totally have underestimated this. Well, at least now I know! Thanks :) – Merott Sep 26 '18 at 21:11
  • What exactly do you need this for? – Bergi Sep 26 '18 at 21:21
  • @NinaScholz: It's not just cosmetic. The individual groups are sets, not lists (which is why OP has their members in ascending order). If it were permutations, then OP would have 30414093201713378043612608166064768844377641568960512000000000000 possibilities instead of 49120458506088132224064306071170476903628800. Not that the difference is important in practice :-), although it could be with a smaller problem size. You can generate the partitions using permutations of a multiset, which is easy enough (but different). – rici Sep 26 '18 at 21:23
  • @rici, it looks like a view to the data. it does not change the algorithm, just the presentation. – Nina Scholz Sep 26 '18 at 21:27
  • @Nina: Look at OP's example with 7 items. If you generated all the permutations, you'd have 5040 partitions in the output, not 210. That's not just a view. – rici Sep 26 '18 at 21:32
  • This is the type of search space you need a quantum computer for, you are not going to get anywhere asking JavaScript to search such a massive space. – Adrian Brand Sep 26 '18 at 23:39

2 Answers2

0

Proof of concept ...

You could use the factorial of the length of the array as helper for getting the wanted permutation.

Basically this algorithm calculates the indices of the array and reassembles the result upon.

The subsets array is just cosmetically.

This approach is slow, because it generates the nth permutaion. A faster approach could be to go on with the last permuatation and go on with the next.

function getN(n, array, subsets) {
    var f,
        l = array.length,
        indices = [],
        temp;

    array = array.slice();
    while (l--) {
        f = factorial(l);
        indices.push(Math.floor(n / f));
        n %= f;
    }
    temp = indices.map(i => array.splice(i, 1)[0]);
    return subsets
        ? subsets.map((i => l => temp.slice(i, i += l))(0))
        : temp;


}

function factorial(num) {
    var result = 1;
    while (num) {
        result *= num;
        num--;
    }
    return result;
}

var i, l,
    array = ['a', 'b', 'c', 'd', 'e', 'f', 'g'],
    subsets = [3, 2, 2],
    pre = document.getElementById('out');

for (i = 0, l = factorial(array.length); i < l; i++) {
    pre.innerHTML += i.toString().padStart(4) +': ' + JSON.stringify(getN(i, array, subsets)) + '\n';
}
<pre id="out"></pre>
Nina Scholz
  • 376,160
  • 25
  • 347
  • 392
0

If you're looking to combine all possible combination values (cartesian product), you can use the product() function of the lodash framework : 

var allCombinations = _.product(
       /* RequestState    */[RequestState.Completed, RequestState.Failed, RequestState.PartiallyCompleted, RequestState.Canceled, RequestState.Available, RequestState.InProgress],
       /* ApprovalState   */[ApprovalState.Denied, ApprovalState.WaitingForApproval],
       /* hasAccessToCase */[true, false],
       /* IsRequestOwner  */[true, false],
       /* categoryId*/      [1, 2, 3],
    );

with the example above, this will result in an array of 6x2x2x2x3 = 144 combinations

You can then iterate over all combination with array forEach : 

allCombinations.forEach(([requestState, approvalState, hasAcccesToCase,  isRequestOwner, categoryId]) => {

     (...)

});
Jean-Sébastien Gervais
  • 899
  • 10
  • 12