algorithm - 生成具有所有唯一 k 位子序列的所有 n 位序列。

Question

我发现了这个问题:

Consider sequences of 36 bits. Each such sequence has 32 5 - bit sequences consisting of adjacent bits. For example, the sequence 1101011… contains the 5 - bit sequences 11010,10101,01011,…. Write a program that prints all 36 - bit sequences with the two properties: 1.The first 5 bits of the sequence are 00000. 2. No two 5 - bit subsequences are the same.

于是我泛化寻找所有具有k-bit唯一子序列的n-bit序列满足上述要求。然而，我能想到的唯一方法是使用残酷的强制搜索:生成前 k 位为零的 n 位序列的所有排列，然后对于每个序列，检查所有 k 位子序列是否唯一。这显然不是一种非常有效的方法。我想知道有没有更好的方法来解决这个问题？

谢谢。

Answer 1

最简单的方法似乎是回溯方法。您可以跟踪使用平面数组看到的 5 位序列。在每一位，尝试添加 0 -- counter = (counter & 0x0f) << 1并检查你以前是否看过，然后执行 counter = counter | 1并尝试这条路。

可能有更高效的算法可以更快地修剪搜索空间。这似乎与 https://en.wikipedia.org/wiki/De_Bruijn_sequence 有关.我不确定，但我相信它实际上是等价的；也就是说，序列的最后五位数字必须是 10000 , 使其循环。

编辑:这是一些 C 代码。由于递归，它在空间方面的效率低于它可能的效率，但很简单。最糟糕的是掩码管理。看来我对 De Bruijn 序列的看法是正确的；这会找到所有 2048 个。

#include <stdio.h>
#include <stdlib.h>

char *binprint(int val) {
    static char res[33];
    int i;
    res[32] = 0;
    for (i = 0; i < 32; i++) {
        res[31 - i] = (val & 1) + '0';
        val = val >> 1;
    }
    return res;
}

void checkPoint(int mask, int counter) {
    // Get the appropriate bit in the mask
    int idxmask = 1 << (counter & 0x1f);

    // Abort if we've seen this suffix before
    if (mask & idxmask) {
        return;
    }

    // Update the mask
    mask = mask | idxmask;

    // We're done if we've hit all 32
    if (mask == 0xffffffff) {
        printf("%10u 0000%s\n", counter, binprint(counter));
        return;
    }

    checkPoint(mask, counter << 1);
    checkPoint(mask, (counter << 1) | 1);
}

void main(int argc, char *argv[]) {
    checkPoint(0, 0);
}