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

1 Ansicht (letzte 30 Tage)
Ulrik William Nash am 4 Jun. 2018
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.
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

### Antworten (2)

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 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.
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Ulrik William Nash am 4 Jun. 2018
Of course, permutations. Not combinations.

Melden Sie sich an, um zu kommentieren.

Ulrik William Nash am 4 Jun. 2018
Thank you, Walter Roberson. If I am not mistaken, the following provides the general answer:
partitions(k,ones(1,n),1)
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

### Kategorien

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