谷歌搜索二进制De Bruijn序列算法，我发现了这一点，您实际上可以分辨出发生了什么。它被称为“
FKM算法”（在Fredricksen，Kessler和Maiorana之后），它使用“项链前缀”方法找到了字典上最小的De Bruijn序列。我将使用n
= 4的示例进行说明。

首先，创建所有长度为n的二进制序列，即从0到2 n -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

（你会发现，这将删除所有AO偶数除0000，且大于所有数字0111除1111，这有助于简化代码。）

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

0、0001、0011、01、0111、1

加入序列，您将获得De Bruijn序列：

0000100110101111

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

0000100110101111000

（更多信息： F. Ruskey，J。Sawada，A。Williams：“固定权重二进制字符串的De
Bruijn序列”和B.Stevens，A。Williams：“二进制字符串的最酷顺序”，摘自：“有趣的算法”，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));