通过交换两位(不按字典顺序)排列二进制数字的排列

Question

我正在寻找一种算法,它计算给定长度(n)和位数(k)的位串的所有排列.例如,while n=4和k=2算法应输出:

1100
1010
1001
0011
0101
0110

我知道Gosper的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);
}

(另请参阅[此C++ 11版本] [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的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,sect.7.2.1.3,公式(31)和图 26C.