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

Question

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

0011
0110
0101
1100
1010
1001

在本例中，这种组合的数量被计算为C(n,r)，例如C(4,2)，其结果为6。

请注意，您可以通过将数字从0增加到2^n并查看计数是否正确来解决此问题。然而，这不是一个快速的解决方案。我考虑使用C++中的bitset类来解决问题，并且需要增加N。

我想补充一点，对于这个问题有一个显而易见的递归算法。由于堆栈溢出，它不是一个好的答案。我从Gosper的hack中得到了一个好的答案。但是，由于后续需要扩展输入并可能使用MPI实现，我需要一个可扩展的库。无符号整数不够大，我更喜欢一个可扩展且快速的库，如bitset。在bitset库中没有加法，因此其他解决方案呢？

- Aznaveh

---

虽然“按字典顺序的下一个位排列”在需要在序列中添加一个项目且只知道先前结果时非常高效，但是您可以通过跟踪某些状态来进行动态规划搜索，而无需使用递归（相比之下，“下一个排列”操作每次都必须从数组中恢复状态）。特别是“当前位位置”（作为索引或掩码）、“未放置的零的数量”和“未放置的一的数量”，以及工作中的任意精度数字，就足够了。 - undefined

Answer 1

你可以使用Gosper的技巧实现“字典序下一个比特排列”，具体实现方法请参考这里：

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

- harold

Answer 2

您可以按照以下方式生成它们：

1. 首先，在开头放置n-r个0和r个1（例如，当n=4且r=2时，向量为0011）。 2. 然后，重复以下过程： - 找到最右边的一个1，使其左边有一个0。如果没有这样的1，则完成。 - 将它向左移动（即与0交换位置）。 - 将所有位于它右侧的1移动到向量的末尾。例如，如果我们有0110，则首先将最右边的可移动的1向左移动并得到1010，然后将所有在它右侧的1移动到向量的末尾并得到1001。

此解决方案的时间复杂度为O(C(n, r) * n)，并且具有按字典顺序生成元素的特点。

- kraskevich