Filter löschen
Filter löschen

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

1 Ansicht (letzte 30 Tage)
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.

Antworten (2)

Walter Roberson
Walter Roberson am 4 Jun. 2018
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 . 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
Ulrik William Nash am 4 Jun. 2018
Thank you, Walter Roberson. If I am not mistaken, the following provides the general answer:


Mehr zu Matrices and Arrays 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