algorithm - 没有相等的 n 长度子序列的最长二进制序列

Question

我们正在寻找具有以下标准的算法。

输入是一个任意正整数(n)，表示比较子序列的长度。

我们搜索最长的二进制序列，其中不包含相等的 n 长度子序列。匹配的相等序列可以重叠(当匹配必须不相交时，这也是一个有趣的问题)。输出将是这个位序列。

例如，如果n = 3:

10111010 无效，因为 101 子序列重复。 01010 也无效，因为 010 多次出现。 01101001 是有效的，但显然不是可能的最长序列。

Answer 1

通过谷歌搜索二进制 De Bruijn 序列算法，我发现了这个算法，您可以在其中实际判断发生了什么。被称为“FKM 算法”(在 Fredricksen、Kessler 和 Maiorana 之后)，它使用“项链前缀”方法找到字典序最少的 De Bruijn 序列。我将使用 n=4 的示例进行解释。

首先，创建所有长度为 n 的二进制序列，即从 0 到 2ⁿ-1 的所有数字:

0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111

然后，删除不在最低旋转中的序列，例如0110 可以旋转为更小的 0011:

0000, 0001, 0011, 0101, 0111, 1111

(您会注意到，这会删除除 0000 之外的所有偶数，以及除 1111 之外的所有大于 0111 的数字，这有助于简化代码。)

然后将序列减少到它们的“非周期性前缀”，即如果它们是较短序列的重复，则使用较短的序列；例如0101 是01 的重复，1111 是1 的重复:

0, 0001, 0011, 01, 0111, 1

加入序列，你有一个 De Bruijn 序列:

0000100110101111

对于非循环序列，添加n-1个零:

0000100110101111000

(更多信息:F. Ruskey, J. Sawada, A. Williams: "De Bruijn Sequences for Fixed-Weight Binary Strings" 和 B. Stevens、A. Williams:“The Coolest Order Of Binary Strings”，来自:“Fun With Algorithms”，2012 年，第 327-328 页)

---

我很好奇 FKM 与我的其他算法相比表现如何，所以我编写了这个相当笨拙的 JavaScript 实现。它确实快得多，并在不到一秒的时间内为 N=20 生成 1,048,595 个数字序列。在严肃的语言中，这应该非常快。

function DeBruijnFKM(n) {
    var seq = "0";                                         // start with 0 precalculated
    for (var i = 1; i < n; i++) {                      // i = number of significant bits
        var zeros = "", max = Math.pow(2, i);
        for (var j = n; j > i; j--) zeros += "0";                   // n-i leading zeros
        for (var k = i > 1 ? max / 2 + 1 : 1; k < max; k += 2) {     // odd numbers only
            var bin = k.toString(2);                           // bin = significant bits
            if (isSmallestRotation(zeros, bin)) {
                seq += aperiodicPrefix(zeros, bin);
            }
        }
    }
    return seq + Math.pow(2, n - 1).toString(2);      // append 2^N-1 and trailing zeros

    function isSmallestRotation(zeros, bin) {
        var len = 0, pos = 1;   // len = number of consecutive zeros in significant bits
        for (var i = 1; i < bin.length; i++) {
            if (bin.charAt(i) == "1") {
                if (len > zeros.length) return false;   // more zeros than leading zeros
                if (len == zeros.length
                && zeros + bin > bin.substr(pos) + zeros + bin.substr(0, pos)) {
                    return false;                              // smaller rotation found
                }
                len = 0;
                pos = i + 1;
            }
            else ++len;
        }
        return true;
    }

    function aperiodicPrefix(zeros, bin) {
        if (zeros.length >= bin.length) return zeros + bin;    // too many leading zeros
        bin = zeros + bin;
        for (var i = 2; i <= bin.length / 2; i++) {  // skip 1; not used for 0 and 2^N-1
            if (bin.length % i) continue;
            var pre = bin.substr(0, i);                      // pre = prefix of length i
            for (var j = i; j < bin.length; j += i) {
                if (pre != bin.substr(j, i)) break;              // non-equal part found
            }
            if (j == bin.length) return pre;                      // all parts are equal
        }
        return bin;                                               // no repetition found
    }
}

document.write(DeBruijnFKM(10));