# produce all combinations of n choose k in binary

34 Ansichten (letzte 30 Tage)
NA am 13 Mär. 2020
Kommentiert: Stephen23 am 17 Mär. 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 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

### Akzeptierte Antwort

John D'Errico am 13 Mär. 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 Kommentare6 ältere Kommentare anzeigen6 ältere Kommentare ausblenden
NA am 17 Mär. 2020
Bearbeitet: NA am 17 Mär. 2020
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 am 17 Mär. 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.

Melden Sie sich an, um zu kommentieren.

### Weitere Antworten (2)

Alex Mcaulley am 13 Mär. 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 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

Akira Agata am 13 Mär. 2020
Bearbeitet: Akira Agata am 13 Mär. 2020
Another solution:
n = 5;
k = 3;
A = unique(perms([zeros(1,n-k) ones(1,k)]),'rows');
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

### Kategorien

Mehr zu Dynamic System Models finden Sie in Help Center und File Exchange

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by