An effiient way to isolate permutations of 0's and 1's that sum to k.

I am working on a problem where I need information about all permutations of n coinflips, where the sum of heads is k.

I could use

all = dec2bin(2^n-1:-1:0)-'0'

to obtain all permutations of flips, and from this matrix, I could isolate those rows that sum to k. However, this procedure quickly becomes intractable as n grows.

The question is whether there is a procedure for obtaining all permutations that sum to k, without needing to generate all the other permutations that don’t sum to k.

Answer 1

[Walter Roberson]

There is only one combination of length n in which the number of heads is exactly k.

Your code does not appear to be dealing in combinations: it appears to be dealing in permutations.

It is possible to write the cases more efficiently, by considering the partitions of an integer https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer . The basic idea is that you break up into k 1's and n-k 0's, and you need to partition as patterns of

some non-zero number of 1's, followed by some non-zero number of 0's, followed by 1's, etc,

such that the total number of 1's is k and the total number of 0's is n-k .

If you arrange any one partition of k in non-decreasing order, then you can permute those sizes to get a different overall permutation.

... To be honest, it isn't always worth the trouble. Sometimes a "moving peg" approach is simplier. And in my experience, the dec2bin approach is the most efficient up to total length 29.

[Ulrik William Nash]

Of course, permutations. Not combinations.

Answer 2

[Ulrik William Nash]

Thank you, Walter Roberson. If I am not mistaken, the following provides the general answer:

partitions(k,ones(1,n),1)