大部分平衡双分区的排列

Question

我正在研究一种树搜索算法，其中我使用通过位集表示的元素的二分法，即位集 1000101 表示二分法 {0,2,6} {1,3,4,5}.

目前，我只是通过递增一个位集来遍历所有二分，即遍历集合 {0,1,2,3} 的所有二分，我从 0001（含）到 1000（独占）

由于我的算法有时允许我 'fail fast' 当我找到合适的二分法时，我想重新排序它们以便我首先查看更平衡的二分法。

因此，我想问问是否有人知道从 1 到 2^k 的数字排列，其中 min(#set bits, #unset bits) 或多或少只会减少，这可以仍然可以高效计算.

由于这是一种启发式方法，我不是在寻找准确的结果，只是想稍微加快我的算法速度。

Answer 1

Rory 的评论让我走上了正确的方向：

如果我们从 bitset 中的固定数量开始，我们可以简单地使用一些 bit-twiddling hack 遍历所有这些。

从0...01...1开始，先是k/2，然后是k/2 - 1，k/2 - 2等等。
对于每个起始值，使用 Gosper's Hack 迭代位集的所有可能排列，直到我们到达位集的边界。

一个简单的实现可能看起来像这样（对于 k <= 63）

for (int i = k / 2; i > 0; --i) {
    // start with 0 ... 0 1 ... 1 (i times)
    unsigned int v = (1 << i) - 1;
    // first bitset that doesn't represent a valid bipartition
    unsigned int end = 1 << k;
    // without this, we would count some bipartitions twice for k even
    if (k % 2 == 0 && i == k / 2) end >>= 1;
    while(v < end) {
        // do something with v...
        // iterate to the lexicographically next permutation
        unsigned int t = v | (v - 1);
        v = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
    }
}

大部分平衡双分区的排列

Permutation for mostly balanced bipartitions

algorithm

math

bit-manipulation

heuristics