algorithm - 为给定的长度生成 0's and 1' 的所有组合，给定最小值和最大值 1

Question

我想知道在给定 1 的最小数量和最大数量的情况下，是否存在一种有效的算法来生成长度为 n 的 0 和 1 的所有组合。

例子:

n=4 min=2 max=3

0011 0101 1001 0110 1010 1100 (with 2 1's)
0111 1011 1101 1110           (with 3 1's)

我知道我可以用二进制数从 (n-min)*0(min)*1 到 (max)*1 (n-max)*0(例如 0011 到 1110)并取所有这些那满足约束条件，但我想知道是否有更有效的算法。

Answer 1

有一个简单的算法可以迭代大小 n 和 k 的组合:

1. 从长度为 n 的位向量开始，最后 k 位为 1。
2. 尽可能长地重复(即，直到您获得长度为 n 的位向量，其中前 k 位为 1):A。在位向量中找到最后一个 01 序列。将其更改为 10 并将以下所有 1 位(必须紧随其后)移动到序列的末尾。

有一个简单的无循环位操作 hack 可以做到这一点。你可以在我对这个问题的回答中看到它:Find n-th set of a powerset