7

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

0011
0110
0101
1100
1010
1001

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

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

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

4

2 回答 2

5

您可以使用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（_BitScanForward在 MSVC 上），

unsigned int t = (v | (v - 1)) + 1;  
w = t | ((((t & -t) / (v & -v)) >> 1) - 1);
于 2015-01-03T14:35:46.563 回答
2

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

  1. 最初，制作一个开头有 n - r 个零，最后有 r 个零的向量（0011对于 n = 4 和 r = 2）。

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

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

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

于 2015-01-03T14:12:33.613 回答