produce 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;
   ]

Answer 1

[John D'Errico]

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.

[James Tursa]

Nice

[John D'Errico]

:)

[Akira Agata]

Elegant solution !

[NA]

if n=44 and k=21 is there any way to produce this combination?

Error using zeros
Requested 2012616400080x21 (314898.4GB) array exceeds maximum array size
preference. Creation of arrays greater than this limit may take a long time
and cause MATLAB to become unresponsive. See array size limit or preference
panel for more information.

[NA]

I mean is there any way to decrease this number 2012616400080.

for example produce some combination of n choose k in binary.

[John D'Errico]

I feared this would be a possibility, as people almost always seem to overdo these things.

I'm sorry, but this is simply impossible to do. You cannot use any method to solve your problem, at least not directly. Why not?

There are

nchoosek(44,21)
ans =
             2012616400080

combinations necessary to produce. Worse, since the result will be stored in a double precision array, of size 2012616400080x21, so with 8 bytes per element, you need to have that much addressable memory available as RAM.

And it matters not how you will do the work, you need to store that much stuff. Essentially, your computer would need to have over 300 terabytes of addressable RAM. Worse, since all arrays get copied a couple of times as you use them, that probably means effectively 3 times as much, so roughly 1000 terabytes. All of the other methods proposed will be little better in the end, since they too must store that much stuff as a result. (Ok, maybe you could use loops, and store all results using only one byte per element, which is what MATLAB uses to store logical arrays. But even so, you will still end up needing on the order of 50 terabytes to store it all and work with the resulting array.)

You don't have enough RAM, at least on any computer short of a super computer, costing many millions of dollars. And tomorrow you will ask how to solve a problem just a little bit larger, because research never tries to solve smaller problems. So if you made things just a bit larger...

nchoosek(60,30)*30*8
ans =
      2.83834995755667e+19

Yes, I know, you asked, if you could store the results purely in binary form, so now only 1 bit per element. You are still talking about 44 bits of information per combination. That will means we would need to use an 8 byte integer to store each combination. (There is no 6 byte integer class in MATLAB, nor should there be.)

nchoosek(44,21)
ans =
             2012616400080
             
nchoosek(44,21)*8
ans =
            16100931200640
            
nchoosek(44,21)*8/1024^3
ans =
          14995.1606994867

Does your computer have 14995 gigabytes of adressable RAM? And since as I said, the good rule is to triple that number, you will need on the order of 50 terabytes of adressable free RAM, even if you stored the results quite efficiently.

The point is, you cannot do it. PERIOD.

What can you do? Much of the time when people decide they need to compute huge arrays like this, they are trying to solve some problem in a brute force way. That is, generate all possible combinations that satisfy some target, and then pick the one that make them happy. But as I said, you cannot use brute force to solve this problem.

The answer is to change your approach. That often means to use an optimization tool, that can then search the entire space of interest. But in some way, you need to retreat from brute force.

Mathematics can sometimes be the art of finding elegant ways to solve a problem that may otherwise be intractable.

[NA]

Thank you for your answer.

Is there any way to produce combination one by one?

I have a for loop and on this I use first combination. If first combination meets some condition, I can use it.

If not I go to find second combination.

This for loop stops in some condition. So I do not need to find all 2012616400080 combination.

[Stephen23]

"Is there any way to produce combination one by one?"

Search FEX, e.g.:

https://www.mathworks.com/matlabcentral/fileexchange/24459-next-combination-permutation

Of course you should expect to be waiting a while for any result.

Answer 2

[Alex Mcaulley]

One option (Probably a better implementation can be done, but this one should work):

n = 5;
k = 3;

comb = nchoosek(1:n,k);

res = cell2mat(arrayfun(@(x) myfun(x,n,comb),(1:size(comb,1))','uni',0));

function sol = myfun(i,n,comb)
    sol = zeros(1,n);
    sol(comb(i,:)) = 1;
end

res =

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

Answer 3

[Akira Agata]

Another solution:

n = 5;
k = 3;

A = unique(perms([zeros(1,n-k) ones(1,k)]),'rows');