Iterating over values from fixed sum, in MatLab

Question

Let's say I have n marbles, and each can be one of 8 possible colors. I want to iterate over all possible values of color combinations of the marbles. How can I do this in MatLab?

For example, if n = 2, then I want to iterate through:

2 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 0 0 1 0 0 0 0

1 0 0 0 1 0 0 0

1 0 0 0 0 1 0 0

1 0 0 0 0 0 1 0

1 0 0 0 0 0 0 1

0 2 0 0 0 0 0 0

0 1 1 0 0 0 0 0

0 1 0 1 0 0 0 0

etc.

EDIT:

This is what some pseudocode would look like, but as you can see it's very sloppy. I'm interested in a more concise way of doing this, and one that doesn't need that if statement...

for i8 = 0:1:n
    for i7 = 0:1:n - i8
        for i6 = 0:1:n - i8 - i7
            for i5 = 0:1:n - i8 - i7 - i6
                for i4 = 0:1:n - i8 - i7 - i6 - i5
                    for i3 = 0:1:n - i8 - i7 - i6 - i5 - i4
                        for i2 = 0:1:n - i8 - i7 - i6 - i5 - i4 - i3
                            for i1 = 0:1:n - i8 - i7 - i6 - i5 - i4 - i3 - i2
                                if i1 + i2 + i3 + i4 + i5 + i6 + i7 + i8 == n
                                    i = [i1, i2, i3, i4, i5, i6, i7, i8]
                                end
                            end
                        end
                    end
                end
            end
        end
    end
end

Answer 1

Here is the solution (the code was tested in GNU/Octave, it should work in Matlab as well). This code is derived from Octave-Forge multinom_exp.m

function conf = marbin (nmar,nbin)
%% Returns the position of nmar in nbis, allowing the marbles to be in the same bin.

%% This is standard stars and bars.
 numsymbols = nbin+nmar-1;
 stars = nchoosek (1:numsymbols, nmar);

%% Star labels minus their consecutive position becomes their index
%% position!
 idx = bsxfun (@minus, stars, [0:nmar-1]);

%% Manipulate indices into the proper shape for accumarray.
 nr = size (idx, 1);
 a = repmat ([1:nr], nmar, 1);
 b = idx';
 conf = [a(:), b(:)];
 conf = accumarray (conf, 1);

Answer 2

I think this is easier is you think of the states of the marbles, rather than the states of the colors. Then convert from marble states to color states as needed. For example, if thinking about an ordered list of all possible marble states, you could create function that looks like this (using all zeros as an "all done" flag):

function state = nextmarblestate(state, nMarbles, nColors)
%Increment the marble state by 1

%Add one to the last marble
state(end) = state(end)+1;

%Propogate change towards the first marble as colors overflow
for ixCurrent = nMarbles:-1:2
    if state(ixCurrent) > nColors;
        state(ixCurrent) = 1;
        state(ixCurrent-1) = state(ixCurrent-1)+1;
    else
        return;
    end
end

%Check to see if we are done (reset to 0)
if state(1) > nColors
    state = zeros(1,nMarbles);
end

Then you can write a quick loop to go through all of the marble states like this:

nMarbles = 2;
nColors = 8;

marblestate = ones(1,nMarbles);
while sum(marblestate)>0
    disp(['Marblestate = [' num2str(marblestate) ']'])
    marblestate = nextmarblestate(marblestate, nMarbles, nColors);
end

Or, to get the result you wanted, write a conversion from marble state to color state, like this (sorry for the terseness here, this could be expanded to a prettier version):

marbleState2colorState = @(marblestate) arrayfun(@(color)sum(marblestate==color), 1:nColors);

And then using that conversion function, expand the while loop above like so:

marblestate = ones(1,nMarbles);
while sum(marblestate)>0
    disp(['Marblestate = [' num2str(marblestate) '],  Colorstate = [' num2str(marbleState2colorState(marblestate)) ']'])
    marblestate = nextmarblestate(marblestate, nMarbles, nColors);
end

Which produces the following output:

Marblestate = [1  1],  Colorstate = [2  0  0  0  0  0  0  0]
Marblestate = [1  2],  Colorstate = [1  1  0  0  0  0  0  0]
Marblestate = [1  3],  Colorstate = [1  0  1  0  0  0  0  0]
Marblestate = [1  4],  Colorstate = [1  0  0  1  0  0  0  0]
Marblestate = [1  5],  Colorstate = [1  0  0  0  1  0  0  0]
Marblestate = [1  6],  Colorstate = [1  0  0  0  0  1  0  0]
Marblestate = [1  7],  Colorstate = [1  0  0  0  0  0  1  0]
Marblestate = [1  8],  Colorstate = [1  0  0  0  0  0  0  1]
Marblestate = [2  1],  Colorstate = [1  1  0  0  0  0  0  0]
Marblestate = [2  2],  Colorstate = [0  2  0  0  0  0  0  0]
Marblestate = [2  3],  Colorstate = [0  1  1  0  0  0  0  0]
Marblestate = [2  4],  Colorstate = [0  1  0  1  0  0  0  0]
Marblestate = [2  5],  Colorstate = [0  1  0  0  1  0  0  0]
Marblestate = [2  6],  Colorstate = [0  1  0  0  0  1  0  0]
Marblestate = [2  7],  Colorstate = [0  1  0  0  0  0  1  0]
Marblestate = [2  8],  Colorstate = [0  1  0  0  0  0  0  1]
Marblestate = [3  1],  Colorstate = [1  0  1  0  0  0  0  0]
Marblestate = [3  2],  Colorstate = [0  1  1  0  0  0  0  0]
Marblestate = [3  3],  Colorstate = [0  0  2  0  0  0  0  0]
Marblestate = [3  4],  Colorstate = [0  0  1  1  0  0  0  0]
Marblestate = [3  5],  Colorstate = [0  0  1  0  1  0  0  0]
Marblestate = [3  6],  Colorstate = [0  0  1  0  0  1  0  0]
Marblestate = [3  7],  Colorstate = [0  0  1  0  0  0  1  0]
Marblestate = [3  8],  Colorstate = [0  0  1  0  0  0  0  1]
Marblestate = [4  1],  Colorstate = [1  0  0  1  0  0  0  0]
Marblestate = [4  2],  Colorstate = [0  1  0  1  0  0  0  0]
Marblestate = [4  3],  Colorstate = [0  0  1  1  0  0  0  0]
Marblestate = [4  4],  Colorstate = [0  0  0  2  0  0  0  0]
Marblestate = [4  5],  Colorstate = [0  0  0  1  1  0  0  0]
Marblestate = [4  6],  Colorstate = [0  0  0  1  0  1  0  0]
Marblestate = [4  7],  Colorstate = [0  0  0  1  0  0  1  0]
Marblestate = [4  8],  Colorstate = [0  0  0  1  0  0  0  1]
Marblestate = [5  1],  Colorstate = [1  0  0  0  1  0  0  0]
Marblestate = [5  2],  Colorstate = [0  1  0  0  1  0  0  0]
Marblestate = [5  3],  Colorstate = [0  0  1  0  1  0  0  0]
Marblestate = [5  4],  Colorstate = [0  0  0  1  1  0  0  0]
Marblestate = [5  5],  Colorstate = [0  0  0  0  2  0  0  0]
Marblestate = [5  6],  Colorstate = [0  0  0  0  1  1  0  0]
Marblestate = [5  7],  Colorstate = [0  0  0  0  1  0  1  0]
Marblestate = [5  8],  Colorstate = [0  0  0  0  1  0  0  1]
Marblestate = [6  1],  Colorstate = [1  0  0  0  0  1  0  0]
Marblestate = [6  2],  Colorstate = [0  1  0  0  0  1  0  0]
Marblestate = [6  3],  Colorstate = [0  0  1  0  0  1  0  0]
Marblestate = [6  4],  Colorstate = [0  0  0  1  0  1  0  0]
Marblestate = [6  5],  Colorstate = [0  0  0  0  1  1  0  0]
Marblestate = [6  6],  Colorstate = [0  0  0  0  0  2  0  0]
Marblestate = [6  7],  Colorstate = [0  0  0  0  0  1  1  0]
Marblestate = [6  8],  Colorstate = [0  0  0  0  0  1  0  1]
Marblestate = [7  1],  Colorstate = [1  0  0  0  0  0  1  0]
Marblestate = [7  2],  Colorstate = [0  1  0  0  0  0  1  0]
Marblestate = [7  3],  Colorstate = [0  0  1  0  0  0  1  0]
Marblestate = [7  4],  Colorstate = [0  0  0  1  0  0  1  0]
Marblestate = [7  5],  Colorstate = [0  0  0  0  1  0  1  0]
Marblestate = [7  6],  Colorstate = [0  0  0  0  0  1  1  0]
Marblestate = [7  7],  Colorstate = [0  0  0  0  0  0  2  0]
Marblestate = [7  8],  Colorstate = [0  0  0  0  0  0  1  1]
Marblestate = [8  1],  Colorstate = [1  0  0  0  0  0  0  1]
Marblestate = [8  2],  Colorstate = [0  1  0  0  0  0  0  1]
Marblestate = [8  3],  Colorstate = [0  0  1  0  0  0  0  1]
Marblestate = [8  4],  Colorstate = [0  0  0  1  0  0  0  1]
Marblestate = [8  5],  Colorstate = [0  0  0  0  1  0  0  1]
Marblestate = [8  6],  Colorstate = [0  0  0  0  0  1  0  1]
Marblestate = [8  7],  Colorstate = [0  0  0  0  0  0  1  1]
Marblestate = [8  8],  Colorstate = [0  0  0  0  0  0  0  2]