0

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!

Stewie Griffin
  • 14,889
  • 11
  • 39
  • 70
pap-00
  • 45
  • 3
  • 13
  • 1
    de2bi will convert integers to binary vectors. After knowing that it's just counting... – dave Mar 19 '14 at 01:07
  • First of all thanks a lot.Secondly if i had searched a lit better, i wouldn't have to ask for that,because i just found that thread http://www.mathworks.com/matlabcentral/newsreader/view_thread/237035, and i tested and is exactly what i want.Thank you again dave. – pap-00 Mar 19 '14 at 01:15

2 Answers2

4

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.

Rody Oldenhuis
  • 37,726
  • 7
  • 50
  • 96
  • The `ndgrid` approach (see my answer) seems to be slightly faster than your loop? At least for large `N` – Luis Mendo Mar 19 '14 at 11:26
  • @LuisMendo: I suspect that's because you generate a list of all combinations, and I convert all integers from decimal to binary. Yours is more specific to this problem, and therefore, faster. +1 though :) – Rody Oldenhuis Mar 19 '14 at 13:23
  • @LuisMendo: I just copy-pasted and adjusted from `dec2bin`, whereas you thought a bit more :) – Rody Oldenhuis Mar 19 '14 at 13:24
  • Actually, I copy-pasted too (from a previous [Q&A](http://stackoverflow.com/questions/21895335/generate-a-matrix-containing-all-combinations-of-elements-taken-from-n-vectors)) :-) – Luis Mendo Mar 19 '14 at 20:02
  • Rody , i used dec2bin and worked fine. i also tested and have results for 2^20. Above that was of course impossible for the memory to return any results. – pap-00 May 09 '14 at 16:43
3

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
Community
  • 1
  • 1
Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
  • Based on the resultant matrix, is there any way to dynamically calculate a element value? For example, how to know that (1,1) = 0 without mounting the matrix? – Josué Lima Apr 09 '16 at 23:42
  • 1
    @JosuéLima The columns of row `r` are the binary expansion of `r-1`. For example, for row `3` with `4` columns the elements are `dec2bin(3-1,4)`, or `dec2bin(3-1,4)-'0'` to convert to numbers – Luis Mendo Apr 10 '16 at 01:51