produce all combinations of n choose k in binary

Question

NA 2020-3-13

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/510687-produce-all-combinations-of-n-choose-k-in-binary

评论： Stephen23 2020-3-17

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 0 0;
0 1 0 1;
0 1 1 0;
0 1 1 1;
1 1 1 0;
1 1 0 1;
1 0 0 1;
1 1 0 1;
1 0 1 1;
   ]

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

John D'Errico 2020-3-13

4
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/510687-produce-all-combinations-of-n-choose-k-in-binary#answer_419982

在 MATLAB Online 中打开

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     1     1     1
   1     0     1     1
   0     0     1     1
   1     1     0     1
   0     1     0     1
   1     0     0     1
   1     1     1     0
   0     1     1     0
   1     0     1     0
   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 个评论
显示 6更早的评论隐藏 6更早的评论

John D'Errico 2020-3-16

编辑：John D'Errico 2020-3-16

在 MATLAB Online 中打开

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 2020-3-17

编辑：NA 2020-3-17

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 2020-3-17

"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 2020-3-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/510687-produce-all-combinations-of-n-choose-k-in-binary#answer_419977

在 MATLAB Online 中打开

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 3

Akira Agata 2020-3-13

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/510687-produce-all-combinations-of-n-choose-k-in-binary#answer_419983

编辑：Akira Agata 2020-3-13

在 MATLAB Online 中打开

Another solution:

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

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

produce all combinations of n choose k in binary

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

8 个评论
显示 6更早的评论隐藏 6更早的评论

更多回答（2 个）

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

produce all combinations of n choose k in binary

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

采纳的回答

8 个评论 显示 6更早的评论隐藏 6更早的评论

更多回答（2 个）

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

0 个评论 显示 -2更早的评论隐藏 -2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

WeChat

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

8 个评论
显示 6更早的评论隐藏 6更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

0 个评论
显示 -2更早的评论隐藏 -2更早的评论