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

Question

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

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

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

我想补充一点，这个问题有一个明显的递归算法。由于堆栈溢出，这不是一个好的答案。我从 Gosper 的 hack 那里得到了一个很好的答案。虽然我需要扩大输入并可能稍后使用 MPI 实现，但我需要一个可扩展的库。 Unsigned int 不够大，我更喜欢像 bitset 这样可扩展且快速的库。由于bitset库中没有添加，因此该解决方案不适用于此处。还有其他解决方案吗？

Answer 1

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

首先，创建一个向量，开头有 n - r 个零，结尾有 r 个（0011 for n = 4 and r = 2）。
然后，重复以下步骤：
1. 找到最右边的一个，使零位于它的左边。如果没有这样的，我们就完成了。
2. 向左移动一位（即与零互换）。
3. 将位于右侧的所有元素从它移动到向量的最后。
  比如我们有0110，我们先把最右边能移动的移到左边，得到1010，然后我们把它所有的右移到vector的末尾，得到 1001.

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

Answer 2

您可以使用 Gosper's Hack:

实现 "lexicographically next bit-permutation"

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);

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

What is the fastest algorithm to computer all permutations of a binary number with same hamming weight?

algorithm

combinations

hammingweight