Unique (finite length) combinations of a given set of elements - Implementation in Matlab
combinations, matlab
Solution
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 `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';
Problem
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?