algorithm - 最平衡二分的排列

Question

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

目前，我只需通过递增位集即可迭代所有二分区，即迭代集合 {0,1,2,3} 的所有二分区，我从 0001(含)到 1000(不含)

由于我的算法有时允许我在找到合适的二分区时“快速失败”，因此我想对它们重新排序，以便首先查看更平衡的二分区。

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

由于这是一种启发式方法，因此我并不是在寻找精确的结果，而是在寻找一种稍微加快算法速度的方法。

Answer 1

罗里的评论让我走向了正确的方向:

如果我们从位集中固定数量的位开始，我们可以使用一些位调整技巧简单地迭代所有这些位。

• 从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));
    }
}