構造一個圓包含所有n位二進制數

Question

的問題來自於採訪時： 如何構建一個圓（長度2^N 01輪的序列）包含所有可能的n位二進制數，每個數出現一次和只有一次。例如，當n = 2時，結果爲：

0--0 
| | 
1--1 

數字是{00,01,11,10}。所有可能的數字只出現一次。當n = 3時，下面是一個示例回答：

0--0--1 
/  \ 
0   1 
\  / 
    1--0--1 

Answer 1

您需要構建二進制de Bruijn cycle。維基百科文章建議幾種方法來做到這一點：

這De Bruijn序列可以通過利用n維德Bruijn圖的哈密爾頓路徑超過k個碼元（或等同地，a的歐拉循環（正被構造 - 1）維De Bruijn圖）。

另一種構造方式是按字典順序連接所有Lyndon詞的長度除以n。

De Bruijn序列也可以使用移位寄存器或通過有限域構建。

Answer 2

線性移位反饋寄存器來方便在產生該序列：

以001開始，生成使用LSFR與多項式P（X）= 101 的序列將是「001 1101 001 7個一個位」。 （LSFR的週期爲2^N-1，缺少全零項）

注意到兩端都出現相同的3位序列，我們將用0 - '00111010'。

其中數字0..7發生偏移量是7，0，5，1，6,4，3，2

多項式是通過異或先前的N位的所有位施加多項式有一個的條目。

0 0 1 
xor 1 0 1 => (0 and 1) xor (0 and 0) xor (1 and 1) => 1 

    0 0 1 1 
xor 1 0 1 ==> (0 and 1) xor (1 and 0) xor (1 and 1) => 1 

作爲一般規則，多項式的兩端有1，中間有一個數;人們可以嘗試蠻力搜索缺失的位或谷歌的「伽羅瓦領域中的本原多項式」的綜合列表。