生成最長的位序列，其中所有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可在網上。