CODEWITHSUNDEEP
matlabcombinationsvectorizationpermutation
space_voyager
space_voyager

Reputation: 2034

MATLAB generate all ways that n items can be put into m bins?

I want to find all ways that n items can be split among m bins. For example, for n=3 and m=3 the output would be (the order doesn't matter):

[3 0 0
 0 3 0
 0 0 3
 2 1 0
 1 2 0
 0 1 2
 0 2 1
 1 0 2
 2 0 1
 1 1 1]

The algorithm should be as efficient as possible, preferrably vectorized/using inbuilt functions rather than for loops. Thank you!

Upvotes: 2

Views: 132

Answers (2)

Dev-iL
Dev-iL

Reputation: 24169

I'd like to suggest a solution based on an external function and accumarray (it should work starting R2015a because of repelem):

n = uint8(4); % number of items
m = uint8(3); % number of bins
whichBin = VChooseKR(1:m,n).'; % see FEX link below. Transpose saves us a `reshape()` later.
result = accumarray([repelem(1:size(whichBin,2),n).' whichBin(:)],1);

Where VChooseKR(V,K) creates a matrix whose rows are all combinations created by choosing K elements of the vector V with repetitions.

Explanation:

The output of VChooseKR(1:m,n) for m=3 and n=4 is:

 1     1     1     1
 1     1     1     2
 1     1     1     3
 1     1     2     2
 1     1     2     3
 1     1     3     3
 1     2     2     2
 1     2     2     3
 1     2     3     3
 1     3     3     3
 2     2     2     2
 2     2     2     3
 2     2     3     3
 2     3     3     3
 3     3     3     3

All we need to do now is "histcount" the numbers on each row using positive integer bins to get the desired result. The first output row would be [4 0 0] because all 4 elements go in the 1st bin. The second row would be [3 1 0] because 3 elements go in the 1st bin and 1 in the 2nd, etc.

Upvotes: 1

Luis Mendo
Luis Mendo

Reputation: 112699

This should be pretty efficient.

It works by generating all posible splitings of the real interval [0, n] at m−1 integer-valued, possibly coincident split points. The lengths of the resulting subintervals give the solution.

For example, for n=4 and m=3, some of the possible ways to split the interval [0, 4] at m−1 points are:

  • Split at 0, 0: this gives subintervals of lenghts 0, 0, 4.
  • Split at 0, 1: this gives subintervals of lenghts 0, 1, 3.
  • ...
  • Split at 4, 4: this gives subintervals of lenghts 4, 0, 0.

Code:

n = 4; % number of items
m = 3; % number of bins
x = bsxfun(@minus, nchoosek(0:n+m-2,m-1), 0:m-2); % split points
x = [zeros(size(x,1),1) x n*ones(size(x,1),1)]; % add start and end of interval [0, n]
result = diff(x.').'; % compute subinterval lengths

The result is in lexicographical order.

As an example, for n = 4 items in m = 3 bins the output is

result =
     0     0     4
     0     1     3
     0     2     2
     0     3     1
     0     4     0
     1     0     3
     1     1     2
     1     2     1
     1     3     0
     2     0     2
     2     1     1
     2     2     0
     3     0     1
     3     1     0
     4     0     0

Upvotes: 7

Related Questions