Unique (finite length) combinations of a given set of elements - Implementation in Matlab

Question

I have the following problem. I need to reproduce all the unique combinations of 0s and 1s that include exactly m zeros and exactly n ones. For example if I have 2 zeros and 3 ones the combinations I am looking for are the 10 following:

1) 0 0 1 1 1

2) 0 1 0 1 1

3) 0 1 1 0 1

4) 0 1 1 1 0

5) 1 0 0 1 1

6) 1 0 1 0 1

7) 1 0 1 1 0

8) 1 1 0 0 1

9) 1 1 0 1 0

10) 1 1 1 0 0

Right now, I am using A=perms([0 0 1 1 1]) and then unique(A,'rows') but this is really time consuming if the length of the vector is more than 10. Can anybody think of a more efficient solution?

score 3 · Accepted Answer · edited May 23 '17 at 11:49

Approach 1:

Generate all "combinations" of m+n elements taken from the set [0 1]. This can be done efficiently using this approach.
Keep only those combinations that contain n ones.

Code:

m = 7; %// number of zeros
n = 9; %// number of ones
L = m+n;
vectors = repmat({[0 1]}, 1, L);
combs = cell(1,L);
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1});
combs = cat(L+1, combs{:});
combs = reshape(combs,[],L);
combs = combs(sum(combs,2)==n,:);

Example result for m=2; n=3:

combs =
     0     0     1     1     1
     0     1     0     1     1
     0     1     1     0     1
     0     1     1     1     0
     1     0     0     1     1
     1     0     1     0     1
     1     0     1     1     0
     1     1     0     0     1
     1     1     0     1     0
     1     1     1     0     0

Approach 1 modified

To save memory, use uint8 values in step 1, and convert to double at the end of step 2:

m = 7; %// number of zeros
n = 9; %// number of ones
L = m+n;
vectors = repmat({uint8([0 1])}, 1, L);
combs = cell(1,L);
[combs{end:-1:1}] = ndgrid(vectors{end:-1:1});
combs = cat(L+1, combs{:});
combs = reshape(combs,[],L);
combs = double(combs(sum(combs,2)==n,:));

Approach 2:

Similar to approach 1, but in step 1 generate all combinations as binary expressions of all integers from 0 to 2^(m+n)-1, using dec2bin. This produces a char array, so it should be as memory-efficient as approach 1 modified. Then, step 2 should be slightly adapted to use chars, and a final conversion to numeric values is required:

m = 7; %// number of zeros
n = 9; %// number of ones
combs = dec2bin(0:2^(m+n)-1);
combs = combs(sum(combs=='1',2)==n,:)-'0';

Unique (finite length) combinations of a given set of elements - Implementation in Matlab

1 Answers1