MATLAB: Produce all combinations of n choose k in binary

find all combinations of n choose k in binary

I have

n=5; 
k=3;

I want to have combinations of n choose k in binary

result should be (5 choose 3=10) (the order does not matter)

A=[1 0 0 1 1;
   1 1 1 0 0;
   1 0 1 0 1;
   1 0 1 1 0;
   0 0 1 1 1;
   0 1 1 1 0;
   0 1 1 0 1;
   1 1 0 0 1;
   0 1 1 0 1;
   0 1 0 1 1;
   ]

Best Answer

This is easier than you may think, as long as you think outside of the box just a bit.

n = 5;
k = 3;
dec2bin(sum(nchoosek(2.^(0:n-1),k),2)) - '0'
ans =
     0     0     1     1     1
     0     1     0     1     1
     1     0     0     1     1
     0     1     1     0     1
     1     0     1     0     1
     1     1     0     0     1
     0     1     1     1     0
     1     0     1     1     0
     1     1     0     1     0
     1     1     1     0     0

The nice thing is, you do not need to generate a long list of all binary numbers, then keep only those that have exactly three bits turned on.

The above scheme should work for up to 52 bit results, since MATLAB can encode integers as large as 2^53-1 in a double. And, of course, if k is at all large, then things will get nasty for n>52. Anyway, I don't think dec2bin will be successful in more than 52 bits though, even if you tried to use uint64.

Related Solutions

MATLAB: Binary matrix that contains specific number of zeros in each row

At most 2 zeros out of 4 is easy.

nchoosek(4,0) + nchoosek(4,1) + nchoosek(4,2)
ans =
    11

So 11 possibilities. If the numbers get larger, then it will still be very nasty. So 50 columns, with as many as 10 zeros is still on the order 1e10 rows in that matrix, and a total memory required on the order of 4e12 bytes (4 terabytes of RAM, just to store that array.) You would not be able to do this.

But for reasonable problems where I will not create the full factorial as it is too large for you, it is easy enough. Just do it constructively. A loop will be sufficient here.

ncols = 4;
nzmax = 2;
mat = ones(1,ncols);
for n = 1:nzmax
  zloc = nchoosek(1:ncols,n);
  m = size(zloc,1);
  matn = ones(m,ncols);
  matn(sub2ind(size(matn),repmat((1:m)',[1,n]),zloc)) = 0;
  mat = [mat;matn];
end
mat
mat =
     1     1     1     1
     0     1     1     1
     1     0     1     1
     1     1     0     1
     1     1     1     0
     0     0     1     1
     0     1     0     1
     0     1     1     0
     1     0     0     1
     1     0     1     0
     1     1     0     0

MATLAB: How to generate an array of binary data of this form

It might not be the most beautiful algorithm in the world, but this works (on 64 bit MATLAB) for even N values up to at least

N = 20, giving 184756 rows in 15 seconds
N = 22, giving 705432 rows in 106 seconds.
N = higher might be possible, if you are patient enough and have enough memory...

but keep in mind that at some point you will simply run out of memory.

It is easy to check that all rows sum to the requested value. In contrast there is no obvious way to check if any rows are missing, but I did notice that the number of rows matches exactly with OEIS A000984, which might have some relevance.

N = 12;
M = [0,1;1,0];
for k = 3:N
    R = size(M,1);
    M = [zeros(R,1),M;ones(R,1),M;M,zeros(R,1);M,ones(R,1)];
    M = unique(M(sum(M,2)<=N/2,:),'rows');
end
M = M(sum(M,2)==N/2,:);

For N=12 this gives:

>> size(M)
ans =
   924    12
>> M
ans =
     0     0     0     0     0     0     1     1     1     1     1     1
     0     0     0     0     0     1     0     1     1     1     1     1
     0     0     0     0     0     1     1     0     1     1     1     1
     0     0     0     0     0     1     1     1     0     1     1     1
     0     0     0     0     0     1     1     1     1     0     1     1
     0     0     0     0     0     1     1     1     1     1     0     1
     0     0     0     0     0     1     1     1     1     1     1     0
     0     0     0     0     1     0     0     1     1     1     1     1
     0     0     0     0     1     0     1     0     1     1     1     1
... lots of rows here
     1     1     1     1     0     1     0     0     1     0     0     0
     1     1     1     1     0     1     0     1     0     0     0     0
     1     1     1     1     0     1     1     0     0     0     0     0
     1     1     1     1     1     0     0     0     0     0     0     1
     1     1     1     1     1     0     0     0     0     0     1     0
     1     1     1     1     1     0     0     0     0     1     0     0
     1     1     1     1     1     0     0     0     1     0     0     0
     1     1     1     1     1     0     0     1     0     0     0     0
     1     1     1     1     1     0     1     0     0     0     0     0
     1     1     1     1     1     1     0     0     0     0     0     0

PS: of course recursive algorithms for generating permutations are simple but when I tried some with added short-circuit behavior for repeated rows, they were significantly slower than the above loop.

Best Answer

Related Solutions

MATLAB: Binary matrix that contains specific number of zeros in each row

MATLAB: How to generate an array of binary data of this form

Related Question