How to fill an array with all possible combinations of 0 and 1?

Question

I have an algorith that the number of possibles combinations of 0 and 1, can reach the number 2^39. Let's say i have n=2 situations, or n1=2^2=4 combinations of 0 and 1: 00,01,10,11.From that i can create an array a=zeros(n,n1) and fill the columns with the possible combinations? That means first column has 00,second 01,third 10,last 11.I want this to be dynamic that means that n can be 1,2,3...,39, show the array will be a=zeros(n,2^n).Thanks for any response!

Answer 1

Just for general understanding: why do you think you need an array of all combinations of all integers from 0 to 2³⁹? That array would consume 39×2³⁹/1000⁴ ≈ 21TB of RAM...last time I checked, only the world's most advanced supercomputers have such resources, and most people working with those machines consider generating arrays like this quite wasteful...

Anyway, for completeness, for any N, this is the simplest solution:

P = dec2bin(0:(2^N)-1)-'0'

But, a little piece of advice: dec2bin outputs character arrays. If you want numerical arrays, you can subtract the character '0', however, that gives you an array of doubles according to the rules of MATLAB:

>> P = dec2bin(0:(2^3)-1)-'0';
>> whos P
  Name      Size            Bytes  Class     Attributes

  P         8x3               192  double                      

If you want to minimize your memory consumption, generate a logical array instead:

>> P = dec2bin(0:(2^3)-1)=='1';
>> whos P
  Name      Size            Bytes  Class      Attributes

  P         8x3                24  logical     

If you want to also speed up the execution, use the standard algorithm directly:

%// if you like cryptic one-liners
B1 = rem(floor((0:pow2(N)-1).' * pow2(1-N:0)), 2) == 1;

%// If you like readability
B = false(N,pow2(N));
V = 0:pow2(N)-1;
for ii = 1:N
    B(ii,:) = rem(V,2)==1;
    V = (V-B(ii,:))/2;
end

That last one (the loop) is fastest of all solutions for any N (at least on R2010b and R2013a), and it has the smallest peak memory (only 1/Nth of the cryptic one-liner).

So I'd go for that one :) But, that's just me.

Answer 2

Using ndgrid with a comma-separated list as output (see also here):

[c{1:N}] = ndgrid(logical([0 1]));
c = cat(N+1,c{N:-1:1});
c = reshape(c,[],N);

Example: N=4 gives

c =

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