我们正在寻找具有以下标准的算法。
输入是一个任意的正整数(n(，表示比较子序列的长度。
我们搜索最长的二进制序列，它不包含相等的n长度子序列。匹配的相等序列可以重叠(当匹配必须不相交时，这也是一个有趣的问题(。输出将是这个位序列。
例如，如果n = 3：
10111010无效，因为子序列101重复。 01010也是无效的，因为多次出现010。 01101001是有效的，但显然不是最长的可能序列。
谷歌搜索二进制De Bruijn序列算法，我找到了这个，你可以真正知道发生了什么。它被称为"FKM算法"(在Fredricksen，Kessler和Maiorana之后(，它使用"项链前缀"方法找到词典上最少的De Bruijn序列。我将使用 n=4 的示例进行解释。
首先，创建长度为 n 的所有二进制序列，即从 0 到 2n-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二进制字符串"和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));使用免费的 Minizinc 约束求解器，您可以按如下方式编写对给定序列长度的搜索：
int: n = 3;
int: k = pow(2,n)+n-1;
array[1..k] of var 0..1: a;
constraint
forall (i in 1..k-n) (
forall (j in i+1..k-n+1) (
exists (x in 0..n-1)(
a[i+x] != a[j+x]
)
)
);
solve satisfy;
output [show(a[m]) | m in 1..k];
对于n=3，最长序列是
1110100011
k=11产生UNSATISFIABLE
子序列长度 n=3 的 k=10 位上找到序列需要 71 毫秒。对于子序列长度 n=9，总序列为 520 位，时间为 6.1 秒。
n位线性反馈移位寄存器如果能够以最长周期工作，则必须满足大多数要求。 这是因为其操作状态是测试窗口的大小。 如果位模式发生不止一次，那么它的状态将恢复到以前的状态，并且它的周期将比预期的短。
不幸的是，LFSR 不能以零状态运行。 要解决此问题，只需将零附加到位字符串的开头即可。
void generate(int n) {
static const uint64_t polytab[64] = {
0x2, 0x2, 0x6, 0xc,
0x18, 0x28, 0x60, 0xc0,
0x170,0x220, 0x480, 0xa00,
0x1052, 0x201a, 0x402a, 0xc000,
/* table can be completed from:
* http://www.xilinx.com/support/documentation/application_notes/xapp052.pdf
*/
};
uint64_t poly = polytab[n];
uint64_t m = ~(-2ll << (n - 1));
uint64_t s = 1;
for (i = 0; i < n; i++) emit(0);
do {
emit(s & 1);
s <<= 1;
s = (s + parity(s & poly)) & m;
} while (s != 1);
}
测试窗口，那么只需使用 64 位(或者如果必须，您可以将算术扩展到 128 位(。 超过 64 位，在发现位字符串不是最大长度之前，其他一些资源将被耗尽。
为了完整起见，奇偶校验函数：
int parity(uint64_t m) {
int p = 0;
while (m != 0) {
m &= m - 1;
p ^= 1;
}
return p;
}
n=3、4 和 5 的输出：
3: 0001011100
4: 0000100110101111000
5: 000001001011001111100011011101010000
在找到 FKM 算法之前，我摆弄了一个简单的递归算法，该算法尝试 0 和 1 的所有组合并返回(按字典顺序(第一个结果。我发现这种方法很快就会耗尽内存(至少在浏览器中的 JavaScript 中(，所以我试图根据这些观察提出一个改进的非递归版本：
-
通过运行从 0 到 2 N-1 的 N 长度二进制字符串，并检查它们是否已经存在于序列中，如果不存在，则检查它们是否与序列的末尾部分重叠，您可以使用N 长度块而不是每位构建字典顺序最小的二进制 De Bruijn 序列。
-
您只需要遍历最多 2 个N-1-1 的 N 长度二进制字符串，然后附加 2个 N-1 而不重叠。不需要检查以"1"开头的 N 长度字符串。
-
您可以跳过大于 2 的偶数;它们是序列中已有的较小数字的位移版本。需要数字 2 以避免 1 和 3 错误重叠;在代码方面，您可以通过在已经就位的 0、1 和 2 开始序列来解决此问题(例如
0000010为 N=5(，然后迭代从 3 开始的每个奇数。
N=5 的示例：
0 00000
1 00001
2 00010
3 00011
4 (00100)
5 00101
6 (00110)
7 00111
8 (01000)
9 (01001)
10 (01010)
11 01011
12 (01100)
13 01101
14 (01110)
15 01111
+10000
=> 000001000110010100111010110111110000
如您所见，序列是用00000到01111的字符串和附加的10000构建的，10001到11111的字符串不需要检查。所有大于 2 的偶数都可以跳过(数字 9 和 13 也可以跳过(。
此代码示例演示了 JavaScript 中的简单实现。它很快达到 N=14 左右，如果您有几分钟的时间，它会为 N=20 提供所有 1,048,595 个字符。
function binaryDeBruijn(n) {
var zeros = "", max = Math.pow(2, n - 1); // check only up to 2^(N-1)
for (var i = 1; i < n; i++) zeros += "0";
var seq = zeros + (n > 2 ? "010" : "0"); // start with 0-2 precalculated
for (var i = 3; i < max; i += 2) { // odd numbers from 3
var part = (zeros + i.toString(2)).substr(-n, n); // binary with leading zeros
if (seq.indexOf(part) == -1) { // part not already in sequence
for (var j = n - 1; j > 0; j--) { // try partial match at end
if (seq.substr(-j, j) == part.substr(0, j)) break; // partial match found
}
seq += part.substr(j, n); // overlap with end or append
}
}
return seq + "1" + zeros; // append 2^(N-1)
}
document.write(binaryDeBruijn(10));除了偶数之外，还有其他数字可以跳过(例如示例中的数字 9 和 13(;如果你能预测这些数字，这当然会使算法更有效率，但我不确定那里是否有明显的模式。