生成最长的位序列，其中所有5位连续的子序列都是唯一的

Question

生成最长的位序列（每个槽只有0或1）。

在这个序列中，所有连续的m-bit子序列是不同的。

例如，如果m = 2，那么00110是这样一个最长的序列。所有2位子序列都是唯一的：00011110。

---

使用蛮力就一定能够找到一个m这样的序列。

但是，有没有一个聪明的方法？

Answer 1

你可以找到解决方案：邀请离散数学 Matousek和Nesetril第140页（btw。最漂亮的书籍之一）。

答案是惊人的：2 ^k每个k> = 1（在你的情况32）。 我举：

定义以下面的方式的曲线图G =（V，E）：（％）V是组0和长度的1秒k的所有序列的 - 1（％）的有向边缘都对形式的（K-1） - 数位序列（（的，...，一个 _K-1），（A 2 ，...，一个_ķ） ）。定向边与k位序列具有双射对应关系（a ，...，a _k）。

然后它是足够G.

---

编辑 找到一个欧拉环游他们把序列，如果它的结束和开始都粘。例如。从0110得到00我们从最后一个数字开始，然后下一个数字是序列的第一个数字。 因此，序列实际上可以通过将第一个（k-1）数字附加到末尾来扩展。

Answer 2

这被称为De Bruijn sequence。

似乎已经有很多的这些研究，但不幸的是，结果大多stuckbehindpaywalls

我发现one paper可在网上。