All possible combinations of 0's and 1's
14 views (last 30 days)
Show older comments
Hi,
I have a vector of 0's and 1's, say a, and I want to find all possible vectors B of 0's and 1's for which b <= a, for all b in B.
For example, a trivial case where a has only 4 elements.
a = [1, 0, 0, 1]
would give all of the following b's.
b = [0, 0, 0, 0]
b = [1, 0, 0, 0]
b = [0, 0, 0, 1]
b = [1, 0, 0, 1]
I could easily write a loop that starts filling zero 1's, then continues with filling one 1's, two 1's, etc. and then check whether all(b <= a), but I was wondering if there is a smarter way to achieve this.
Thank you!
Robert
0 Comments
Answers (3)
James Tursa
on 23 Feb 2018
Edited: James Tursa
on 23 Feb 2018
One way:
s = 2^sum(a);
result = repmat(a,s,1); % or result = zeros(s,size(a,2));
result(:,logical(a)) = dec2bin(0:s-1)-'0';
But keep in mind that the memory requirements for this grows very quickly as the number of 1's in a increases. So the number of 1's in a must be small enough for this to be a practical approach.
0 Comments
Guillaume
on 23 Feb 2018
Edited: Guillaume
on 23 Feb 2018
a = [1, 0, 0, 1]
sets = {0, [0 1]};
combsets = sets(a + 1);
[combsets{:}] = ndgrid(combsets{:});
combsets = reshape(cat(numel(a)+1, combsets{:}), [], numel(a));
This uses ndgrid to generate all combinations, which will refuse to work if the number of combinations is significant.
Note that at no point will the above generate a combination where b > a to later discard it, so it's going to be a lot more efficient than your prospective loop.
0 Comments
Francesco Onorati
on 24 Apr 2019
Edited: Francesco Onorati
on 24 Apr 2019
Let's assume you need a vector of l_word = 4 elements, each of them can be a 0 or a 1.
l_word = 4;
n_letters = 2;
s = repmat((0:n_letters - 1), 1, l_word);
C = unique(nchoosek(s, l_word), 'rows');
C is a matrix of all words of length 4 you can build using letters 0 and 1. You can change l_word and n_letters.
5 Comments
Francesco Onorati
on 25 Apr 2019
Hi I think it is still wrong
C =
0 0 0 0
1 1 1 1
0 0 0 0
1 1 1 1
0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 1
0 1 0 1
0 1 0 1
0 1 0 1
0 1 0 1
0 0 1 1
0 0 1 1
0 0 1 1
0 0 1 1
Guillaume
on 25 Apr 2019
Doh!
l_word = 4;
n_letters = 2;
C = cell(1, l_word);
[C{:}] = ndgrid(0:n_letters - 1);
C = reshape(cat(l_word+1, C{:}), [], l_word)
Correct and tested this time.
See Also
Categories
Find more on Spectral Measurements in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!