All possible combinations of 0's and 1's

22 次查看（过去 30 天）
Robert Vullings
Robert Vullings 2018-2-23
评论： Guillaume 2019-4-25
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

请先登录，再回答此问题。

回答（3 个）

James Tursa
James Tursa 2018-2-23
编辑：James Tursa 2018-2-23
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.
Guillaume
Guillaume 2018-2-23
编辑：Guillaume 2018-2-23
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.
Francesco Onorati
Francesco Onorati 2019-4-24
编辑：Francesco Onorati 2019-4-24
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 个评论
显示 3更早的评论
Francesco Onorati
Francesco Onorati 2019-4-25
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
Guillaume 2019-4-25
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.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 MATLAB Coder 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by