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

Question

Ulrik William Nash 2018-6-4

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/403899-an-effiient-way-to-isolate-permutations-of-0-s-and-1-s-that-sum-to-k

编辑： Ulrik William Nash 2018-6-4

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 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Walter Roberson 2018-6-4

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/403899-an-effiient-way-to-isolate-permutations-of-0-s-and-1-s-that-sum-to-k#answer_323101

在 MATLAB Online 中打开

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.