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}}

Answer 1

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.