没有相等的 n 长度子序列的最长二进制序列
Longest binary sequence with no equal n-length subsequences
我们正在寻找符合以下标准的算法。
输入为任意正整数(n)，表示比较子序列的长度。
我们搜索最长的二进制序列，其中不包含相等的n长度子序列。匹配的相等序列可以重叠（当匹配必须不相交时，这也是一个有趣的问题）。输出将是这个位序列。
例如，如果 n = 3:
10111010 无效，因为 101 子序列重复。 01010 也无效，因为 010 多次出现。 01101001 是有效的，但显然不是最长的序列。
使用免费的 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，在6.1s内找到了总长度为520位的序列。
谷歌搜索二进制 De Bruijn 序列算法，我找到了这个算法，您可以在其中实际判断发生了什么。被称为 "FKM algorithm"（在 Fredricksen、Kessler 和 Maiorana 之后），它使用 "necklace prefix" 方法找到字典序最少的 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
（您会注意到这会删除 a.o。除 0000 之外的所有偶数，以及除 1111 之外的所有大于 0111 的数字, 这有助于简化代码。)
然后将序列缩减为 "aperiodic prefix"，即如果它们是较短序列的重复，则使用较短的序列；例如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));
一个n位linear feedback shift register，如果能工作在最大周期，肯定满足大部分要求。这是因为它的运行状态是测试大小window。如果一个位模式出现不止一次，那么它的状态就会恢复到以前的状态，并且它的周期会比预期的要短。
不幸的是，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);
}
如果您需要 window 长于 64 位的测试，则只需使用 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 的每个组合以及 returns（按字典顺序）第一个结果。我发现这种方法很快就会耗尽内存（至少在浏览器中 JavaScript 是这样），所以我试图根据这些观察得出一个改进的非递归版本：
通过运行遍历0到2N-1的N个长度的二进制串，并检查它们是否已经存在于序列，如果不是，则检查它们是否与序列的末尾部分重叠，您可以构建字典序最小的二进制 De Bruijn 序列，具有 N 长度块而不是每个位。
只需要遍历N长度的二进制串最多2N-1-1，然后追加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）；如果您可以预测这些数字，这当然会使算法更加高效，但我不确定那里是否存在明显的模式。
我们正在寻找符合以下标准的算法。
输入为任意正整数(n)，表示比较子序列的长度。
我们搜索最长的二进制序列，其中不包含相等的n长度子序列。匹配的相等序列可以重叠（当匹配必须不相交时，这也是一个有趣的问题）。输出将是这个位序列。
例如，如果 n = 3:
10111010 无效，因为 101 子序列重复。 01010 也无效，因为 010 多次出现。 01101001 是有效的，但显然不是最长的序列。
使用免费的 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，在6.1s内找到了总长度为520位的序列。
谷歌搜索二进制 De Bruijn 序列算法，我找到了这个算法，您可以在其中实际判断发生了什么。被称为 "FKM algorithm"（在 Fredricksen、Kessler 和 Maiorana 之后），它使用 "necklace prefix" 方法找到字典序最少的 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
（您会注意到这会删除 a.o。除 0000 之外的所有偶数，以及除 1111 之外的所有大于 0111 的数字, 这有助于简化代码。)
然后将序列缩减为 "aperiodic prefix"，即如果它们是较短序列的重复，则使用较短的序列；例如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));
一个n位linear feedback shift register，如果能工作在最大周期，肯定满足大部分要求。这是因为它的运行状态是测试大小window。如果一个位模式出现不止一次，那么它的状态就会恢复到以前的状态，并且它的周期会比预期的要短。
不幸的是，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);
}
如果您需要 window 长于 64 位的测试，则只需使用 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 的每个组合以及 returns（按字典顺序）第一个结果。我发现这种方法很快就会耗尽内存（至少在浏览器中 JavaScript 是这样），所以我试图根据这些观察得出一个改进的非递归版本：
通过运行遍历0到2N-1的N个长度的二进制串，并检查它们是否已经存在于序列，如果不是，则检查它们是否与序列的末尾部分重叠，您可以构建字典序最小的二进制 De Bruijn 序列，具有 N 长度块而不是每个位。
只需要遍历N长度的二进制串最多2N-1-1，然后追加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）；如果您可以预测这些数字，这当然会使算法更加高效，但我不确定那里是否存在明显的模式。