MATLAB Answers

produce all combinations of n choose k in binary

32 views (last 30 days)
Na
Na on 13 Mar 2020
Commented: Stephen Cobeldick on 17 Mar 2020
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;
]

  0 Comments

Sign in to comment.

Accepted Answer

John D'Errico
John D'Errico on 13 Mar 2020
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.

  8 Comments

Show 5 older comments
John D'Errico
John D'Errico on 16 Mar 2020
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
Na on 17 Mar 2020
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.
Stephen Cobeldick
Stephen Cobeldick on 17 Mar 2020
"Is there any way to produce combination one by one?"
Search FEX, e.g.:
Of course you should expect to be waiting a while for any result.

Sign in to comment.

More Answers (2)

Alex Mcaulley
Alex Mcaulley on 13 Mar 2020
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

  0 Comments

Sign in to comment.


Akira Agata
Akira Agata on 13 Mar 2020
Edited: Akira Agata on 13 Mar 2020
Another solution:
n = 5;
k = 3;
A = unique(perms([zeros(1,n-k) ones(1,k)]),'rows');

  0 Comments

Sign in to comment.

Sign in to answer this question.


Translated by