Generate all possible column vectors in matlab

Question

I am essentially trying to figure out how to generate code for basis vectors of different configurations of M objects into N different states (for example, if I had 2 snacks between 2 kids, I could have (2,0) (0,2) or (1,1), terrible example, but thats the idea)

I am struggling to figure out how to do this without going into many different loops (I want this to be automatic). The idea would be to create a Matrix where each row is a vector of length M. I would start with vec(1) = N then an if loop where if sum(vec) == N, Matrix(1,:)=vec; Then I could take vec(1)=N-i and do the same.

My only issue is I do not see how to use the if and forget it so that if I had maybe 2 objects in 5 locations, how would I do this to get (1 0 0 0 1).

I am not seeing how to do this.

Answer 1

You could use a recursive function:

function out = combos(M,N)

if N == 1
  out = M;
else
  out = [];
  for i = 0:M
    subout = combos(M-i,N-1);
    subout(:,end+1) = i;
    out = [out;subout];
  end
end

Answer 2

I think this does what you want.

The key idea is to generate not the number of elements in each group, but the split points between groups. This can be done via combinations with repetition. Matlab's nchoosek generates combinations without repetition, but these are easily converted into what we need.

M = 5; % number of objects
N = 3; % number of groups
t = nchoosek(1:M+N-1, N-1); % combinations without repetition...
t = bsxfun(@minus, t, 1:N-1); % ...convert into combinations with repetition
t = diff([zeros(size(t,1), 1) t repmat(M, size(t,1), 1) ], [], 2); % the size of each
    % group is the distance between split points

In this example, the result is

t =
     0     0     5
     0     1     4
     0     2     3
     0     3     2
     0     4     1
     0     5     0
     1     0     4
     1     1     3
     1     2     2
     1     3     1
     1     4     0
     2     0     3
     2     1     2
     2     2     1
     2     3     0
     3     0     2
     3     1     1
     3     2     0
     4     0     1
     4     1     0
     5     0     0

Answer 3

This is a similar approach to Luis' without bsxfun. Because we don't like fun.

n = 5;
k = 3;

c = nchoosek(n+k-1, k-1);
result = diff([zeros(c, 1) nchoosek(1:(n+k-1), k-1) ones(c, 1)*(n+k)], [], 2) - 1;

This creates the partitions of the integer n with length k. Given an array of length n + (k-1), we find all combinations of (k-1) places to place partitions between the (unary) integers. For 5 items and 3 locations, we have 7 choices of where to put the partitions:

[ 0 0 0 0 0 0 0 ]

If our chosen combination is [2 4], we replace positions 2 and 4 with partitions to look like this:

[ 0 | 0 | 0 0 0 ]

The O's give the value in unary, so this combination is 1 1 3. To recover the values easily, we just augment the combinations with imaginary partitions at the next values to the left and right of the array (0 and n+k) and take the difference and subtract 1 (because the partitions themselves don't contribute to the value):

diff([0 2 4 8]) - 1
ans =

   1   1   3

By sliding the partitions in to each possible combination of positions, we get all of the partitions of n.

Output:

result =

   0   0   5
   0   1   4
   0   2   3
   0   3   2
   0   4   1
   0   5   0
   1   0   4
   1   1   3
   1   2   2
   1   3   1
   1   4   0
   2   0   3
   2   1   2
   2   2   1
   2   3   0
   3   0   2
   3   1   1
   3   2   0
   4   0   1
   4   1   0
   5   0   0