这是真实发生过的，2023年11月14日，旅行者1号就和地球失去了联系，更准确的说法是它仍然可以接受来自地球的命令，但是不再把“可读的科学与工程数据”发回地球，简单来说就是这小子已读不回，不给家里打电话了。
旅行者1号上有三台机载计算机，被称为飞行数据子系统，简称FDS，这三台计算机负责把一些科学和工程数据进行打包，再发送给地球。但这次三台计算机都出现了某种程度上的故障。
在查找根源问题时，他们发现是里面的一个芯片出现了故障，这个芯片用来储存FDS系统的内存和软件代码，而这些代码就是用来打包数据的。问题是故障芯片没有办法修复，最后工程团队想到了一个办法，就是把这个芯片上储存的代码分成更小的单位，然后把切小的代码分别放置在不同的位置，同时调整部分代码，确保它们即使分家了，仍然可以一起工作。
这解决方案听起来也不怎么高大上，但难度却不低。
第一，NASA喷气推进实验室解释说：“首先，团队要挑选出负责打包航天器工程数据的代码，并于4月18日将其发送到FDS内的新位置。无线电信号大约需要22.5小时才能到达距离地球240亿公里的旅行者1号，而验证能否成功接收信号还需要再等待22.5小时。”这就意味着当你把代码发出去，就只能开始祈祷，等过了45小时，才能知道旅行者1号有没有收到。当然，45小时是最短时间，信号还有可能在路上走丢了。
第二，比距离长更麻烦的是，旅行者1号是1977年发射的，航天器机载计算机听起来很高大上，但我去查了一下这些机器的配置，它只有一台8通道的磁带记录仪和一台储存空间只有低端iPhone手机24万分之一的电脑，毫不夸张地说，现在很多幼儿园孩子手里拿的电子毛绒狗的机器配置，都比旅行者1号的电脑高多了。
第三，旅行者1号所携带的代码是47年前写的，那时还是用二进制0和1的硬编码，现在的工程团队去修这种代码，那可真是包出浆来的祖传老代码啊。非顶尖水平的程序员谁敢接这种活儿，万一不小心写错一个字母，让旅行者1号从此消失在茫茫宇宙中，那这个程序员肯定会被钉在人类历史的耻辱柱上。要知道旅行者1号还能向地球发送信号，靠的是一个功率只有23瓦的发射器，23瓦是什么概念呢？基本上相当于大家冰箱里的灯泡功率。
4月20日，当团队收到旅行者1号的回复时，确认已经修改成功，团队一起鼓掌庆祝，NASA还把团队庆祝图发在了社交媒体上。
让人唏嘘。科技的发展，最重要的是思路与思维。#nasa##科技#
https://t.cn/A6TEHd7P
旅行者1号上有三台机载计算机，被称为飞行数据子系统，简称FDS，这三台计算机负责把一些科学和工程数据进行打包，再发送给地球。但这次三台计算机都出现了某种程度上的故障。
在查找根源问题时，他们发现是里面的一个芯片出现了故障，这个芯片用来储存FDS系统的内存和软件代码，而这些代码就是用来打包数据的。问题是故障芯片没有办法修复，最后工程团队想到了一个办法，就是把这个芯片上储存的代码分成更小的单位，然后把切小的代码分别放置在不同的位置，同时调整部分代码，确保它们即使分家了，仍然可以一起工作。
这解决方案听起来也不怎么高大上，但难度却不低。
第一，NASA喷气推进实验室解释说：“首先，团队要挑选出负责打包航天器工程数据的代码，并于4月18日将其发送到FDS内的新位置。无线电信号大约需要22.5小时才能到达距离地球240亿公里的旅行者1号，而验证能否成功接收信号还需要再等待22.5小时。”这就意味着当你把代码发出去，就只能开始祈祷，等过了45小时，才能知道旅行者1号有没有收到。当然，45小时是最短时间，信号还有可能在路上走丢了。
第二，比距离长更麻烦的是，旅行者1号是1977年发射的，航天器机载计算机听起来很高大上，但我去查了一下这些机器的配置，它只有一台8通道的磁带记录仪和一台储存空间只有低端iPhone手机24万分之一的电脑，毫不夸张地说，现在很多幼儿园孩子手里拿的电子毛绒狗的机器配置，都比旅行者1号的电脑高多了。
第三，旅行者1号所携带的代码是47年前写的，那时还是用二进制0和1的硬编码，现在的工程团队去修这种代码，那可真是包出浆来的祖传老代码啊。非顶尖水平的程序员谁敢接这种活儿，万一不小心写错一个字母，让旅行者1号从此消失在茫茫宇宙中，那这个程序员肯定会被钉在人类历史的耻辱柱上。要知道旅行者1号还能向地球发送信号，靠的是一个功率只有23瓦的发射器，23瓦是什么概念呢？基本上相当于大家冰箱里的灯泡功率。
4月20日，当团队收到旅行者1号的回复时，确认已经修改成功，团队一起鼓掌庆祝，NASA还把团队庆祝图发在了社交媒体上。
让人唏嘘。科技的发展，最重要的是思路与思维。#nasa##科技#
https://t.cn/A6TEHd7P
#上班[超话]# 我看是写着文案的小编脑子和屁股对调了，我猜你这也是如厕时编辑，一不小心把脑子拉出去了，写了坨史出来恶心人，我上班不为钱难道为了你的马？真实的社会现象不揭露，光写点洗脑鸡汤，还有见人的机会，我看是有贱人的机会，真得睁大眼睛看看哪里有规律的生活，规律上班，不规律下班，为什么上班一定不会堕落，为什么不上班又一定会堕落，这种非黑即白的二进制傻逼脑回路能不能去死一死啊，别什么都发出来恶心人
轉桶，糾錯碼，圖論，梵文詩律和 DNA 測序
這兩天有個人問了我一道離散數學題目，大意是這樣的。假設有一個環形的轉筒，邊上被分成 n 塊，如图1所示，這些小塊上可以放 0 或 1 兩個數字。桶外在三個連續的小塊上接了幾根線可以測出這三個塊裡分別是什麼數字。那麼對於 8 個塊，能否設計一個小塊上的數字順序，讓測得的 8 種可能遍歷 0-7 的二進制位，也就是遍歷 000,001,010,011,100,101,110,111 ?
對於 2^3 的情況很好設計，從右上方開始依次填入 10001011，但對於要讀出 4 個二進制位，也就是填入 2^4=16 個數字的方案則很一下子難想出來，更別說對於 k 個的一般情況了。
那麼怎麼解決這個問題呢？
在解決這個問題之前，這個首尾相接的桶的形狀讓我聯想到一種糾錯碼，即循環碼（cyclic code），這是漢明碼的一種，特點在於一列數字 (a0,a1,....,an) （一般 ai 取 0 或1）如果是合格的碼字，那麼經過輪輪換後也是合格的碼字，即 (an,a0,....,a_{n-1}) 這樣的也是合格的。循環碼的容錯率很好。那麼循環碼是如何工作的，又特別在哪裡？在這裡我們需要先岔開主線看看似乎和這個問題毫無關聯的糾錯碼。
循環碼的原理是這樣的，如果我們將碼字 (a0,a1,....,an) 看成一個多項式的係數，即找到一個多項式 cn = a0+a1x+a2x^2+...+anx^n, 那麼我們認為碼字循環後給出的多項式 cn'= a^n+a0x+...+a_{n-1}x^n 和原多項式 cn 是等價的。這就意味著循環碼對應的多項式構成了一個多項式環 R=GF(2)/(x^n-1), 因為很容易看出等價的多項式之間的等價關係是 cn' = x cn - c_{n-1}(x^n-1), 也即意味著等價關係是模掉多項式 x^n-1。既然如此，我們只需要知道 x^n-1 的全部素因子多項式就可以生成整個循環多項式的多項式環！以 8 個碼位為例，x^7-1 的全部素因子為 x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)。我們稱這樣的素因子（的乘積）為循環碼的生成多項式。現在我們來看生成多項式是如何構造循環碼的：例如我們選擇 g(x)=x^3+x+1 作為循環碼的生成多項式，現在我們想傳送四位信息，例如 1101（這是碼字）。碼字對應的多項式為 m(x)=x^3+x^2+1, 要構造一個循環碼，需要先將碼字多項式乘以循環碼多項式的最高項次數，再加上模掉生成多項式的餘數多項式。在這個例子中，即 x^3m(x)+x^3m(x)/g(x) = x^6+x^5+x^3+1 ，再轉換成二進制碼字就得到了一個合法的循環碼，這裡就是 11010001。我們可以發現這樣的循環碼做一次輪換後得到的碼字，即 10100011（對應的多項式 x^6+x^4+x+1） 或 11101000（對應的多項式 x^6+x^5+x^4+x^2） 都是合法的碼字（能被生成多項式 g(x) 整除）。這個生成多項式對應的糾錯碼正好是著名的 [7,4] 漢明碼。對於長度微 7 的二進制循環碼，由於 x^7-1 正好有 3 個素因子，因此共有 2^3=8 個生成多項式。
那麼這個循環碼跟我們想要求的桶上的數字列又有什麼關係呢？注意到當 k=3 的時候，我們的數字列正好是 00011101， 這正好對應了之前給出的生成多項式 x^4+x^3+x^2+1 = (x+1)(x^3+x+1)（與此同時仔細觀察，這裡的數字和我們上一段中用的例子得到的碼字結果也是一樣的，這並不完全是巧合）！於是一個自然的想法產生了，會不會能遍歷所有二進制位的轉筒數會在其對應的循環碼的某個生成多項式中出現？於是迅速寫程序驗證 k=4 的情況，並且非常順利得得到了答案 1001101011110000（如图2所示）。查閱相關定理後，我認為這個事情是正確的，即只要找到生成多項式中的遍歷二進製位的那個就可以了，這比起暴力搜尋，在計算復雜度上小了非常非常多的量級。
但是如果我想要給出一個構造性的表達式，應該怎麼做呢？讓我們把視角從糾錯碼轉到另一個數學領域：圖論。如何用圖論解決這個問題？注意到兩個相鄰的二進制數中，例如 011 和 111 中有兩位是重合的，前者的後兩位和後者的前兩位一致，後者的最後一位是 0 或 1 皆可。那麼很自然想到我們可以用一個有向圖來描繪這個問題，其中頂點是不同的二進制數，方向從前指向後，每個頂點發出兩條邊，接收兩條邊。例如三個二進制位的圖如图3所示。那麼我們的問題就變成了求這個有向圖中的一條閉合路徑，這個路徑恰好經過所有頂點！這樣經過所有頂點的路徑在圖論中被稱作哈密頓環，而尋找一個有向圖的哈密頓環在計算機中是可以實現的，例如我們給出的圖中的一個哈密頓環如图4所示。將給出的哈密頓環的頂點鏈接起來我們就得到了正確的序列，例如根據三個二進制位的圖我們可以得到 k=4 的序列。
事情結束了嗎？不，還沒有。雖然我們看上去大幅度化簡了問題，但其實求解一個給定有向圖中的哈密頓環在計算機中是一個 NP hard 的問題（算法複雜度大概是O(2^n*n^2)），而我們還不能對於給定任意的 k, 用簡單的方法給出想要的序列。經過我查閱資料後，發現我們要求的序列是所謂的德佈魯因（De Bruijn）序列的一個特殊情況。n 階德佈魯因序列的定義是，對於給定的有 n 個字母的字母表 A(在我們的情況中，字母表只有 0 和 1 兩個數字)，其子序列中會出現長度為 m 的子序列且只出現一次，這樣的德佈魯因序列被記成 B(n,m)。我們要求的序列就是 B(2,k)。這個德佈魯因序列看上去十分數學，但其實在各個方面都有大用處。實際上，最早的德佈魯因序列出現在梵文詩律中！
事情是這樣的。印度詩歌在賓伽羅（piṅgala, पिङ्गल ）的著作《詩律經》（Chandaḥsūtra，छन्दःसूत्र）後，每個三音節的元音的長短模式都有特定的名字，例如用 y(य) 表示短-長-長的音節，m(म) 表示長-長-長的音節。那麼為了記住這些可能得模式，印度語言學家 Pāṇini(पाणिनि)[1] 發明了一個詞彙：
yamātārājabhānasalagām
यमाताराजभानसलगं
注意到這個單詞裡，所有的三音節的長短模式出現且僅僅出現一次，例如 yamātā(यमाता) 是短-長-長音節模式，mātārā(मातारा) 是長-長-長音節模式等等。這正是一個德佈魯因序列！
是的，正如我在標題中所寫，下面我要提德佈魯因序列和圖論在 DNA 測序中的應用了。現在假設給你一個環形的脫氧核苷酸序列，如图6(a)所示。在當下最流行的下一代測序法（next generation sequencing, NGS）中，取代傳統的 Sagner 測序法，我們將一串鹼基序列切成很多短的鹼基片段。這些鹼基片段長度相同，但是我們並不知道它們是怎麼從原始的鹼基序列中被切下來的。現在如果我們要從這些片段中復原，應該如何做？沒錯，就是利用剛才的方法，把這些鹼基片段做成一個有向圖，然後在其中尋找合適的哈密頓環，即可重構原來的 DNA 序列。但事實上情況會稍微有些不同，剛剛我們說過，哈密頓環是遍歷個圖中所有頂點的路徑，電腦需要尋找這樣的方案的算法複雜度是很高的。但是如果將這個問題轉化成歐拉環——即著名的一筆畫問題：尋找一個方案遍歷一個圖中所有的邊，如图6(d)所示——計算成本就會大大下降。在現代計算機中，簡單的算法就可以在數十億節點的巨大圖中高效找到歐拉循環，這樣就可以避免 NP 問題的泥潭。使用歐拉環具體是怎麼實現的呢？例如現在我們有一些片段 ATG TGG GGC TGC...... 我們只需要看少一位的片段 AT 後面能接什麼可能的方案，在這裡 ATG 就是 AT 後面接 G ，那麼我們就在頂點 AT 上畫上一條有向邊 ATG 指向 TG 開頭的頂點，而 TG 開頭的序列有 TGG 和 TGC, 那麼我們就從 TG 出發畫兩條線指向 GG 和 GC 。以此類推獲得整張圖。用這樣的片段重構出來的歐拉環我們也稱之為德布魯因圖。
現在回到德布魯因序列上，那麼我們應當如何構造一個德布魯因序列呢？事實上有一個簡單到令人發指的方法：使用林登詞（Lyndon Word）。什麼是林登詞呢？我們先給定一個字典，其中的字母之間是有序關係的，我們稱之為字典序（lexicographic order）。例如字典 {0,1} 就自然帶了一個字典序。所謂的林登詞就是在任何的輪換（比如 101 → 110）之下字典序最小的元素，換句話說任何輪換操作都會讓這個序列的字典序變大。例如對於 0 和 1 兩個字母， 001 就是一個林登詞，因為它在旋轉下會變成 100 或 010，這兩個都比 001 大。對於 0 和 1，不同長度的林登詞可以組成一個無限序列：
0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
那麼如何使用林登詞序列構造一個n-德布魯因序列呢？只需要將長度整除 n 的林登詞按照字典序接在一起就可以了！例如 n=6, 我們則需要總長度為 2^6=64 的德布魯因序列，那麼我們把長度為 1,2,3,6 的林登詞找出來：
0,1,01,001,011,000001,000011,000101,000111,001011,001101,001111,010111,011111
並把它們按照字典序排列並接在一起
0 000001 000011 000101 000111 001 001011 001101 001111 01 010111 011 011111 1
我們就直接得到了總長度為 64 的德布魯因序列！這真是出人意料的簡單。真是令人嗟歎，這樣一個看似複雜，鏈接各個領域的問題居然會有這麼簡單的解法。而且解法巧妙，卻又自然，但這樣簡單的拼接法直到 20 世紀才被人意識到。這林登詞也是個奇物，林登詞按照標準分解可以構造自由李代數，從而將組合問題和代數問題巧妙結合起來，同時這些代數又跟特殊函數、斯特林數從而和量子力學裡的 normal ordering 有關（熟悉量子力學的同學都知道，玻色算符的 normal ordering 可以使用第二類斯特林數和貝爾數刻畫）。
現在我們來回顧一下我們的旅程，從轉鼓出發，我們先是看到了循環糾錯碼，從而引申到了環論域論的世界；隨後使用圖論，將各個問題轉化為尋找哈密頓環；最後來到了組合數學中的德佈魯因序列，利用林登詞將問題巧妙解決，同時德布魯因序列也聯繫了梵語詩律和 DNA 測序。感謝數學。
[1] 此人非常神，早在公元前四世紀就體係化了梵語語法，構詞法。甚至有人認為他的作品標志著語言學的開始。喬姆斯基和各路語言學家也總是在生成語法中致敬 Pāṇini。在優選論中，關於在特殊和一般約束之間的關係的假設被稱為「波你尼約束等級定理」。
這兩天有個人問了我一道離散數學題目，大意是這樣的。假設有一個環形的轉筒，邊上被分成 n 塊，如图1所示，這些小塊上可以放 0 或 1 兩個數字。桶外在三個連續的小塊上接了幾根線可以測出這三個塊裡分別是什麼數字。那麼對於 8 個塊，能否設計一個小塊上的數字順序，讓測得的 8 種可能遍歷 0-7 的二進制位，也就是遍歷 000,001,010,011,100,101,110,111 ?
對於 2^3 的情況很好設計，從右上方開始依次填入 10001011，但對於要讀出 4 個二進制位，也就是填入 2^4=16 個數字的方案則很一下子難想出來，更別說對於 k 個的一般情況了。
那麼怎麼解決這個問題呢？
在解決這個問題之前，這個首尾相接的桶的形狀讓我聯想到一種糾錯碼，即循環碼（cyclic code），這是漢明碼的一種，特點在於一列數字 (a0,a1,....,an) （一般 ai 取 0 或1）如果是合格的碼字，那麼經過輪輪換後也是合格的碼字，即 (an,a0,....,a_{n-1}) 這樣的也是合格的。循環碼的容錯率很好。那麼循環碼是如何工作的，又特別在哪裡？在這裡我們需要先岔開主線看看似乎和這個問題毫無關聯的糾錯碼。
循環碼的原理是這樣的，如果我們將碼字 (a0,a1,....,an) 看成一個多項式的係數，即找到一個多項式 cn = a0+a1x+a2x^2+...+anx^n, 那麼我們認為碼字循環後給出的多項式 cn'= a^n+a0x+...+a_{n-1}x^n 和原多項式 cn 是等價的。這就意味著循環碼對應的多項式構成了一個多項式環 R=GF(2)/(x^n-1), 因為很容易看出等價的多項式之間的等價關係是 cn' = x cn - c_{n-1}(x^n-1), 也即意味著等價關係是模掉多項式 x^n-1。既然如此，我們只需要知道 x^n-1 的全部素因子多項式就可以生成整個循環多項式的多項式環！以 8 個碼位為例，x^7-1 的全部素因子為 x^7-1 = (x+1)(x^3+x+1)(x^3+x^2+1)。我們稱這樣的素因子（的乘積）為循環碼的生成多項式。現在我們來看生成多項式是如何構造循環碼的：例如我們選擇 g(x)=x^3+x+1 作為循環碼的生成多項式，現在我們想傳送四位信息，例如 1101（這是碼字）。碼字對應的多項式為 m(x)=x^3+x^2+1, 要構造一個循環碼，需要先將碼字多項式乘以循環碼多項式的最高項次數，再加上模掉生成多項式的餘數多項式。在這個例子中，即 x^3m(x)+x^3m(x)/g(x) = x^6+x^5+x^3+1 ，再轉換成二進制碼字就得到了一個合法的循環碼，這裡就是 11010001。我們可以發現這樣的循環碼做一次輪換後得到的碼字，即 10100011（對應的多項式 x^6+x^4+x+1） 或 11101000（對應的多項式 x^6+x^5+x^4+x^2） 都是合法的碼字（能被生成多項式 g(x) 整除）。這個生成多項式對應的糾錯碼正好是著名的 [7,4] 漢明碼。對於長度微 7 的二進制循環碼，由於 x^7-1 正好有 3 個素因子，因此共有 2^3=8 個生成多項式。
那麼這個循環碼跟我們想要求的桶上的數字列又有什麼關係呢？注意到當 k=3 的時候，我們的數字列正好是 00011101， 這正好對應了之前給出的生成多項式 x^4+x^3+x^2+1 = (x+1)(x^3+x+1)（與此同時仔細觀察，這裡的數字和我們上一段中用的例子得到的碼字結果也是一樣的，這並不完全是巧合）！於是一個自然的想法產生了，會不會能遍歷所有二進制位的轉筒數會在其對應的循環碼的某個生成多項式中出現？於是迅速寫程序驗證 k=4 的情況，並且非常順利得得到了答案 1001101011110000（如图2所示）。查閱相關定理後，我認為這個事情是正確的，即只要找到生成多項式中的遍歷二進製位的那個就可以了，這比起暴力搜尋，在計算復雜度上小了非常非常多的量級。
但是如果我想要給出一個構造性的表達式，應該怎麼做呢？讓我們把視角從糾錯碼轉到另一個數學領域：圖論。如何用圖論解決這個問題？注意到兩個相鄰的二進制數中，例如 011 和 111 中有兩位是重合的，前者的後兩位和後者的前兩位一致，後者的最後一位是 0 或 1 皆可。那麼很自然想到我們可以用一個有向圖來描繪這個問題，其中頂點是不同的二進制數，方向從前指向後，每個頂點發出兩條邊，接收兩條邊。例如三個二進制位的圖如图3所示。那麼我們的問題就變成了求這個有向圖中的一條閉合路徑，這個路徑恰好經過所有頂點！這樣經過所有頂點的路徑在圖論中被稱作哈密頓環，而尋找一個有向圖的哈密頓環在計算機中是可以實現的，例如我們給出的圖中的一個哈密頓環如图4所示。將給出的哈密頓環的頂點鏈接起來我們就得到了正確的序列，例如根據三個二進制位的圖我們可以得到 k=4 的序列。
事情結束了嗎？不，還沒有。雖然我們看上去大幅度化簡了問題，但其實求解一個給定有向圖中的哈密頓環在計算機中是一個 NP hard 的問題（算法複雜度大概是O(2^n*n^2)），而我們還不能對於給定任意的 k, 用簡單的方法給出想要的序列。經過我查閱資料後，發現我們要求的序列是所謂的德佈魯因（De Bruijn）序列的一個特殊情況。n 階德佈魯因序列的定義是，對於給定的有 n 個字母的字母表 A(在我們的情況中，字母表只有 0 和 1 兩個數字)，其子序列中會出現長度為 m 的子序列且只出現一次，這樣的德佈魯因序列被記成 B(n,m)。我們要求的序列就是 B(2,k)。這個德佈魯因序列看上去十分數學，但其實在各個方面都有大用處。實際上，最早的德佈魯因序列出現在梵文詩律中！
事情是這樣的。印度詩歌在賓伽羅（piṅgala, पिङ्गल ）的著作《詩律經》（Chandaḥsūtra，छन्दःसूत्र）後，每個三音節的元音的長短模式都有特定的名字，例如用 y(य) 表示短-長-長的音節，m(म) 表示長-長-長的音節。那麼為了記住這些可能得模式，印度語言學家 Pāṇini(पाणिनि)[1] 發明了一個詞彙：
yamātārājabhānasalagām
यमाताराजभानसलगं
注意到這個單詞裡，所有的三音節的長短模式出現且僅僅出現一次，例如 yamātā(यमाता) 是短-長-長音節模式，mātārā(मातारा) 是長-長-長音節模式等等。這正是一個德佈魯因序列！
是的，正如我在標題中所寫，下面我要提德佈魯因序列和圖論在 DNA 測序中的應用了。現在假設給你一個環形的脫氧核苷酸序列，如图6(a)所示。在當下最流行的下一代測序法（next generation sequencing, NGS）中，取代傳統的 Sagner 測序法，我們將一串鹼基序列切成很多短的鹼基片段。這些鹼基片段長度相同，但是我們並不知道它們是怎麼從原始的鹼基序列中被切下來的。現在如果我們要從這些片段中復原，應該如何做？沒錯，就是利用剛才的方法，把這些鹼基片段做成一個有向圖，然後在其中尋找合適的哈密頓環，即可重構原來的 DNA 序列。但事實上情況會稍微有些不同，剛剛我們說過，哈密頓環是遍歷個圖中所有頂點的路徑，電腦需要尋找這樣的方案的算法複雜度是很高的。但是如果將這個問題轉化成歐拉環——即著名的一筆畫問題：尋找一個方案遍歷一個圖中所有的邊，如图6(d)所示——計算成本就會大大下降。在現代計算機中，簡單的算法就可以在數十億節點的巨大圖中高效找到歐拉循環，這樣就可以避免 NP 問題的泥潭。使用歐拉環具體是怎麼實現的呢？例如現在我們有一些片段 ATG TGG GGC TGC...... 我們只需要看少一位的片段 AT 後面能接什麼可能的方案，在這裡 ATG 就是 AT 後面接 G ，那麼我們就在頂點 AT 上畫上一條有向邊 ATG 指向 TG 開頭的頂點，而 TG 開頭的序列有 TGG 和 TGC, 那麼我們就從 TG 出發畫兩條線指向 GG 和 GC 。以此類推獲得整張圖。用這樣的片段重構出來的歐拉環我們也稱之為德布魯因圖。
現在回到德布魯因序列上，那麼我們應當如何構造一個德布魯因序列呢？事實上有一個簡單到令人發指的方法：使用林登詞（Lyndon Word）。什麼是林登詞呢？我們先給定一個字典，其中的字母之間是有序關係的，我們稱之為字典序（lexicographic order）。例如字典 {0,1} 就自然帶了一個字典序。所謂的林登詞就是在任何的輪換（比如 101 → 110）之下字典序最小的元素，換句話說任何輪換操作都會讓這個序列的字典序變大。例如對於 0 和 1 兩個字母， 001 就是一個林登詞，因為它在旋轉下會變成 100 或 010，這兩個都比 001 大。對於 0 和 1，不同長度的林登詞可以組成一個無限序列：
0, 1, 01, 001, 011, 0001, 0011, 0111, 00001, 00011, 00101, 00111, 01011, 01111, ...
那麼如何使用林登詞序列構造一個n-德布魯因序列呢？只需要將長度整除 n 的林登詞按照字典序接在一起就可以了！例如 n=6, 我們則需要總長度為 2^6=64 的德布魯因序列，那麼我們把長度為 1,2,3,6 的林登詞找出來：
0,1,01,001,011,000001,000011,000101,000111,001011,001101,001111,010111,011111
並把它們按照字典序排列並接在一起
0 000001 000011 000101 000111 001 001011 001101 001111 01 010111 011 011111 1
我們就直接得到了總長度為 64 的德布魯因序列！這真是出人意料的簡單。真是令人嗟歎，這樣一個看似複雜，鏈接各個領域的問題居然會有這麼簡單的解法。而且解法巧妙，卻又自然，但這樣簡單的拼接法直到 20 世紀才被人意識到。這林登詞也是個奇物，林登詞按照標準分解可以構造自由李代數，從而將組合問題和代數問題巧妙結合起來，同時這些代數又跟特殊函數、斯特林數從而和量子力學裡的 normal ordering 有關（熟悉量子力學的同學都知道，玻色算符的 normal ordering 可以使用第二類斯特林數和貝爾數刻畫）。
現在我們來回顧一下我們的旅程，從轉鼓出發，我們先是看到了循環糾錯碼，從而引申到了環論域論的世界；隨後使用圖論，將各個問題轉化為尋找哈密頓環；最後來到了組合數學中的德佈魯因序列，利用林登詞將問題巧妙解決，同時德布魯因序列也聯繫了梵語詩律和 DNA 測序。感謝數學。
[1] 此人非常神，早在公元前四世紀就體係化了梵語語法，構詞法。甚至有人認為他的作品標志著語言學的開始。喬姆斯基和各路語言學家也總是在生成語法中致敬 Pāṇini。在優選論中，關於在特殊和一般約束之間的關係的假設被稱為「波你尼約束等級定理」。
✋热门推荐