Reputation: 1795
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}}
Upvotes: 0
Views: 483
Reputation: 9997
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 -1
s 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 -1
s should be easy.
Upvotes: 3