生成具有所有唯一 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.

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

谢谢。

Answer 1

我记得在我的编程面试问题书中看到过这个确切的问题。这是他们的解决方案：

希望对您有所帮助。干杯。

Answer 2

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

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

编辑：这是一些 C 代码。由于递归，效率低于 space，但很简单。最糟糕的是掩码管理。看来我对 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);
}

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

Generate all n - bit sequences with all unique k-bit subsequences.

algorithm

bit