2

I would like to know if there is an efficient algorithm to generate all the combinations of 0's and 1's with length n given the minimum and maximum amount of 1's.

Example:

n=4 min=2 max=3

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

I know I could count in binary from (n-min)*0(min)*1 up to (max)*1 (n-max)*0 (0011 up to 1110 for the example) and take all those that satisfy the constraints, but I would like to know if there is an algo that is more efficient.

4

1 回答 1

2

有一个简单的算法用于迭代大小n的组合k：

  1. 从长度为 的位向量开始n，其中最后一位k是1。
  2. 尽可能长地重复（即直到你得到一个长度n为 的位向量，其中第一位k是1）：找到01位向量中的最后一个序列。将其更改为10并将所有后续1位（必须紧随其后）移动到序列的末尾。

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

于 2013-06-02T21:56:45.613 回答