algorithm - 通过交换两位(非字典序)来排列二进制数

Question

我正在寻找一种算法来计算给定长度( n )和位集( k )的位串的所有排列。例如，同时 n=4和 k=2该算法应输出:

1100
1010
1001
0011
0101
0110

我知道 Gosper's Hack 可以按字典顺序生成所需的排列。但是我需要以这样一种方式生成它们，即两个连续的排列仅在两个(或至少恒定数量的)位位置上不同(如上例所示)。
另一个小技巧会很棒，但算法描述也会对我有很大帮助。

Answer 1

走位算法

要通过在每一步中将一个设置位与一个未设置位正好交换来生成二进制序列的排列(即连续排列之间的汉明距离等于 2)，您可以使用这种“行走位”算法；它的工作方式类似于创建(反向)字典顺序，但设置位交替左右移动，因此序列的某些部分被镜像。这可能用一个例子更好地解释:



递归实现

递归算法将接收一个由 n 位组成的序列，其中设置了 k 位，要么全部在左边，要么全部在右边。然后它会保留一个 1最后，对序列的其余部分进行递归，移动设置位并保留 01最后，用其余的位递归，移动设置位并保留 001最后，等等......直到最后一次只有设置位的递归。如您所见，这会创建交替的从左到右和从右到左的递归。
当算法被一个只有一位设置的序列调用时，这是最深的递归级别，设置位从一端走到另一端。



代码示例 1

这是一个简单的递归 JavaScript 实现:

function walkingBits(n, k) {
    var seq = [];
    for (var i = 0; i < n; i++) seq[i] = 0;
    walk (n, k, 1, 0);

    function walk(n, k, dir, pos) {
        for (var i = 1; i <= n - k + 1; i++, pos += dir) {
            seq[pos] = 1;
            if (k > 1) walk(n - i, k - 1, i%2 ? dir : -dir, pos + dir * (i%2 ? 1 : n - i))
            else document.write(seq + "<BR>");
            seq[pos] = 0;
        }
    }
}

walkingBits(7,3);

翻译成 C++ 可能是这样的:

#include <iostream>
#include <string>

void walkingBits(int n, int k, int dir = 1, int pos = 0, bool top = true) {
    static std::string seq;
    if (top) seq.resize(n, '0');
    for (int i = 1; i <= n - k + 1; i++, pos += dir) {
        seq[pos] = '1';
        if (k > 1) walkingBits(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i), false);
        else std::cout << seq << '\n';
        seq[pos] = '0';
    }
    if (top) seq.clear();
}

int main() {
    walkingBits(7, 3);
}

(另请参见 [this C++11 version][3]，作者 VolkerK 在回答有关上述代码的问题时编写。)

(Rextester 似乎被黑了，所以我在下面粘贴了 Volker 的代码。)

#include <iostream>
#include <vector>
#include <functional>

void walkingBits(size_t n, size_t k) {
    std::vector<bool> seq(n, false);
    std::function<void(const size_t, const size_t, const int, size_t)> walk = [&](const size_t n, const size_t k, const int dir, size_t pos){
        for (size_t i = 1; i <= n - k + 1; i++, pos += dir) {
            seq[pos] = true;
            if (k > 1) {
                walk(n - i, k - 1, i % 2 ? dir : -dir, pos + dir * (i % 2 ? 1 : n - i));
            }
            else {
                for (bool v : seq) {
                    std::cout << v;
                }
                std::cout << std::endl;;
            }
            seq[pos] = false;
        }
    };
    walk(n, k, 1, 0);
}

int main() {
    walkingBits(7, 3);

    return 0;
}

代码示例 2

或者，如果您更喜欢实际交换数组元素的代码:

function walkingBits(n, k) {
    var seq = [];
    for (var i = 0; i < n; i++) seq[i] = i < k ? 1 : 0;
    document.write(seq + "<BR>");
    walkRight(n, k, 0);

    function walkRight(n, k, pos) {
        if (k == 1) for (var p = pos + 1; p < pos + n; p++) swap(p - 1, p)
        else for (var i = 1; i <= n - k; i++) {
            [walkLeft, walkRight][i % 2](n - i, k - 1, pos + i);
            swap(pos + i - 1, pos + i + (i % 2 ? 0 : k - 1));
        }
    }
    function walkLeft(n, k, pos) {
        if (k == 1) for (var p = pos + n - 1; p > pos; p--) swap(p - 1, p)
        else for (var i = 1; i <= n - k; i++) {
            [walkRight, walkLeft][i % 2](n - i, k - 1, pos);
            swap(pos + n - i - (i % 2 ? 1 : k), pos + n - i);
        }
    }
    function swap(a, b) {
        var c = seq[a]; seq[a] = seq[b]; seq[b] = c;
        document.write(seq + "<BR>");
    }
}

walkingBits(7,3);

代码示例 3

这里递归被推出到迭代实现中，每个设置位(即每个递归级别)由对象 {o,d,n,p} 表示。它保存从最左边位置的偏移量、设置位移动的方向、位数(即序列这部分的长度)以及设置位在这部分中的当前位置。

function walkingBits(n, k) {
    var b = 0, seq = [], bit = [{o: 0, d: 1, n: n, p: 0}];
    for (var i = 0; i < n; i++) seq.push(0);

    while (bit[0].p <= n - k) {
        seq[bit[b].o + bit[b].p * bit[b].d] = 1;
        while (++b < k) {
            bit[b] = {
                o: bit[b-1].o + bit[b-1].d * (bit[b-1].p %2 ? bit[b-1].n-1 : bit[b-1].p+1),
                d: bit[b-1].d * (bit[b-1].p %2 ? -1 : 1),
                n: bit[b-1].n - bit[b-1].p - 1,
                p: 0
            }
            seq[bit[b].o + bit[b].p * bit[b].d] = 1;
        }
        document.write(seq + "<BR>");
        b = k - 1;
        do seq[bit[b].o + bit[b].p * bit[b].d] = 0;
        while (++bit[b].p > bit[b].n + b - k && b--);
    }
}

walkingBits(7, 3); // n >= k > 0

将字典顺序转换为步行位

由于步行位算法是生成(逆)字典序排列的算法的变体，字典序中的每个排列都可以通过镜像二进制序列的适当部分转换为它在步行位序中的对应排列.
因此，您可以使用任何算法(例如 Gosper's Hack)以字典顺序或反向字典顺序创建排列，然后转换每个排列以获得步行位顺序。



实际上，这意味着从左到右迭代二进制序列，如果您在奇数个零之后找到一个设置位，则反转序列的其余部分并从右到左迭代它，依此类推......

代码示例 4

在下面的代码中 n,k = 7,3 的排列以逆字典序生成，然后一一转换:

function lexi2walk(lex) {
    var seq = [], ofs = 0, pos = 0, dir = 1; 
    for (var i = 0; i < lex.length; ++i) {
        if (seq[ofs + pos * dir] = lex[i]) {
            if (pos % 2) ofs -= (dir *= -1) * (pos + lex.length - 1 - i)
            else ofs += dir * (pos + 1);
            pos = 0;
        } else ++pos;
    }
    return seq;
}

function revLexi(seq) {
    var max = true, pos = seq.length, set = 1;
    while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
    if (pos < 0) return false;
    seq[pos] = 0;
    while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
    return true;
}
    
var s = [1,1,1,0,0,0,0];
document.write(s + " &rarr; " + lexi2walk(s) + "<br>");
while (revLexi(s)) document.write(s + " &rarr; " + lexi2walk(s) + "<br>");

同质灰色路径

该算法创建的排列顺序与 D. Knuth 在 The Art of Computer Programming vol.第 4a 节7.2.1.3，公式(31)&图26c。