algorithm to get all combinations of splitting up N items into K bins

Question

Assuming I have a list of elements [1,2,3,4,] and a number of bins (let's assume 2 bins), I want to come up with a list of all combinations of splitting up items 1-4 into the 2 bins. Solution should look something like this

[{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4}, {1,2,3}}, {{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}, {{}, {1, 2, 3, 4}, {{1, 2, 3, 4}, {}}]

Also, order does matter -- I didn't write out all the return values but {{1, 2, 3}, {4}} is a different solution from {{3, 2, 1}, {4}}

possible duplicate of [Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) — Jay Kominek, Jun 16 '15 at 17:49

score 3 · Accepted Answer · edited May 23 '17 at 10:27

A common approach is as follows.

If you have, say, K bins, then add K-1 special values to your initial array. I will use the -1 value assuming that it never occurs in the initial array; you can choose a different value.

So for your example the initial array becomes arr=[1,2,3,4,-1]; if K were, say, 4, the array would be arr=[1,2,3,4,-1,-1,-1].

Now list all the permutations of array arr. For each permutation, treat all -1s as bin separators, so all the elements befors the first -1 go to the first bin (in that particular order), all the elements between first and second -1 go to the second bin, and so on.

For example:

[-1,1,2,3,4] -> {{}, {1,2,3,4}}
[2,1,3,-1,4] -> {{2,3,4}, {4}}
[3,1,2,-1,4] -> {{3,1,2}, {4}}
[1,3,-1,2,4] -> {{1,3}, {2,4}}

and so on.

Generating all permutation is a standard task (see, for example, Permutations in JavaScript?), and splitting an array by -1s should be easy.

very interesting -- will take a look at this solution – Atul Bhatia Jun 16 '15 at 19:08 — Atul Bhatia, Jun 16 '15 at 19:08

algorithm to get all combinations of splitting up N items into K bins

1 Answers1