遍历所有可能的组合

Question

我的目标是遍历给定数量的1和0的所有组合。再说了，如果我给5号，这将是一个足够快的方式列出

1110100100， 1011000101等

我试图（5 1和5 0的每个不同组合）避免遍历所有可能的排列，并检查5 1是否存在，因为2^n远大于（n选择n/2）。谢谢。

Answer 1

你可以改变这个问题。如果您修复了1（反之亦然），那么这只是您将0的位置放在哪里的问题。对于5 1 s，有5 + 1个垃圾箱，并且您希望将5个元素（0 s）放入垃圾箱中。

这可以通过每个bin的递归和每个bin的循环来解决（把0 ... reaming元素放在bin中 - 除了最后一个bin，你必须放置所有remaning元素）。

Answer 2

想想它的另一种方法是作为string permutation question的一个变体 - 只需构建一个长度为2n的向量（例如111000），然后使用相同的算法进行字符串置换以生成结果。

请注意，天真的算法会打印重复的结果。然而，该算法可以很容易地适应忽略这样的重复，通过在递归函数中保留布尔数组来保持为特定位设置的值。