计算机具有相同汉明权重的二进制数的所有排列的最快算法是什么

Question

我想要一种算法来计算具有给定汉明权重的固定大小二进制数的所有排列。例如，如果汉明权重为 2，二进制大小为 4，则有以下输出：

0011
0110
0101
1100
1010
1001

此类组合的数量计算为此示例中的C(n,r) C(4,2)即 6。

请注意，您只需将一个数字从 0 增加到 2^n 即可解决此问题，然后查看计数是否正常。但是，这不是一个快速的解决方案。我正在考虑在C++中使用位集类解决问题，我需要增加 N。

我想补充一点，这个问题有一个明显的递归算法。由于堆栈溢出，这不是一个好的答案。我从Gosper的黑客中得到了很好的答案。虽然，我需要扩展输入，也许稍后会为此使用 MPI 实现，但我需要一个可扩展的库。无符号 int 不够大，我宁愿像 bitset 这样的可扩展且快速的库。该解决方案在这里不适用，因为位集库中没有添加。还有其他解决方案吗？

Answer 1

您可以使用Gosper的Hack实现"字典顺序下一个位排列"：

unsigned int v; // current permutation of bits 
unsigned int w; // next permutation of bits
unsigned int t = v | (v - 1); // t gets v's least significant 0 bits set to 1
// Next set to 1 the most significant bit to change, 
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));

或者，如果您没有ctz（MSVC 上_BitScanForward），

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);

Answer 2

您可以通过以下方式生成它们：

1. 首先，制作一个开头有 n - r 零，结尾有 r 个零的向量（n = 4 和 r = 2 时为 0011）。

2. 然后，重复以下过程：

   1. 找到最右边的一个，使零位于它的左侧。如果没有这样的，我们就完了。
   2. 将其向左移动（一个位置，即用零交换）。
   3. 将所有位于右侧的从它移动到矢量的最末端。
      例如，如果我们有0110，我们首先移动最右边可以向左移动的那个并得到1010，然后我们将所有向右的从它移动到向量的末尾并得到1001。

此解决方案具有O(C(n, r) * n)时间复杂性。该解决方案的另一个功能：它按字典顺序生成元素。