All possible combinations of 0's and 1's

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

Answer 1

[James Tursa]

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.

Answer 2

[Guillaume]

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.

Answer 3

[Francesco Onorati]

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.

[Guillaume]

That's an extremely inefficient way of generating all permutations of length l of elements of a set of size n. For n = 2 and l = 20, you temporary generate 137,846,528,820 permutations when there are only 1,048,576 unique permutations.

Two better ways of generating the same without any extra work:

l_word = 4;
n_letters = 2;

C = cell(1, l_word);
[C{:}] = ndgrid(0:n_letters - 1);
C = reshape(cat(n_letters, C{:}), [], l_word)

and

l_word = 4;
n_letters = 2;
C = dec2base(0:n_letters^l_word - 1, n_letters) - '0';  %only works for n_letters < 10

[Francesco Onorati]

Hi Guillaume,

it is true, it is very inefficient, but for low values of l_word (max 10) and n_letters (0 and 1, as in the request), I think it is fine. Your version of James Tursa solution is for sure the best so far.

PS: I have tried your first solution, but I suspect there is a bug

C =

     0     0
     1     1
     0     0
     1     1
     0     0
     0     0
     1     1
     1     1
     0     0
     0     0
     0     0
     0     0
     0     1
     0     1
     0     1
     0     1
     0     0
     1     1
     0     0
     1     1
     0     0
     0     0
     1     1
     1     1
     1     1
     1     1
     1     1
     1     1
     0     1
     0     1
     0     1
     0     1

[Guillaume]

Yes, wrong variable used in the reshape. Fixed now.

[Francesco Onorati]

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]

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.