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, which include exactly m zeros and exactly n units. For example, if I have 2 zeros and 3 units, I am looking for the following combinations:

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

At the moment, I use A = waving ([0 0 1 1 1]) and then unique (A, "strings"), but it really takes a lot of time if the length of the vector is greater than 10. Can anyone think of more effective solution?

Answer 1

Approach 1 :

• Generate all "combinations" of elements m+n taken from the set [0 1] . This can be effectively used with this approach .

• Only keep combinations that contain n .

the 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 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 changed

To save memory, use the 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 all combinations are generated as binary expressions of all integers from 0 to 2^(m+n)-1 using dec2bin . This creates a char array, so it should be as memory efficient as modified approach 1. Then step 2 should be slightly adapted to use char s, 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';