74 views (last 30 days)

Show older comments

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;

]

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.

Stephen
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.

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

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');

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

Start Hunting!