對推導(dǎo)不感興趣的老大們可以通過搜索”def”直接跳到代碼實(shí)現(xiàn)部分。不過有閑心還是瞧瞧推導(dǎo)過程的好。我們可以看見好的算法并非無跡可尋，完全依賴某位大牛的靈光閃現(xiàn)，而是通過觀察、歸納、試驗(yàn)、迭代改進(jìn)，逐步雕琢而成。另外，我們時(shí)常感嘆，要是有時(shí)間學(xué)習(xí)算法就好了。要是有時(shí)間仔細(xì)讀讀TAOCP就好了。其實(shí)呢，讀TAOCP也不是搶雞蛋的大事。想讀了，就備好紙筆，調(diào)出趁手的編輯器，打開書，翻到自己感興趣的章節(jié)。遇到公式就推一下。遇到算法就實(shí)現(xiàn) 一下。遇到概念就舉幾個(gè)例子印證一下。遇到難解之處就和Google勾兌一下（不要忘了Google Group，真正的技術(shù)寶藏）。至于一次讀多久，鉆多深，施主隨喜。再說從俺寫的這個(gè)系列可以看出，TAOCP不少章節(jié)也就需要高中知識(shí)，到數(shù)列為止。本來是很美好的事。不必正襟危坐。不必如臨大敵。不必把自己逼得太緊。你會(huì)發(fā)現(xiàn)花的時(shí)間不多，收獲卻不小。

 

上次說到利用遞歸定義生成格雷碼。為了方便，我們把公式重新列一下：

其實(shí)我們也可以用遞推公式定義格雷碼:，明確地給出格雷碼表里每一位格雷碼的表達(dá)式： 。這里的g(k)表示在格雷碼表里排在第k位的格雷碼。其實(shí)，因?yàn)?以 開頭，格雷碼的無限序列是所有非負(fù)整數(shù)的某個(gè)排列：

如果我們把每個(gè)格雷碼看作前面可以填充零的二進(jìn)制整數(shù)，那長度為N的格雷碼序列 包含公式(4)中最前面的2ⁿ個(gè)整數(shù)。只不過每個(gè)整數(shù)前可能填充0，使之長度為N。再把整數(shù)轉(zhuǎn)換成字符串，就生成了相應(yīng)的格雷碼。比如說當(dāng)N＝3時(shí)，第二位格雷碼是001，相當(dāng)于在公式(4)里的第二個(gè)整數(shù)(1)₂前面補(bǔ)上兩個(gè)0后將其轉(zhuǎn)換為字符串，使得該字符串的長度等于3。

當(dāng)k = 2ⁿ + r 且 時(shí)，我們可以從公式(3)得出g(k) = 2ⁿ + g(2ⁿ – 1 – r )。這個(gè)結(jié)論的推導(dǎo)也挺容易：既然k > 2ⁿ, 那么我們知道g(k)一定在 里面。既然 表示將 反轉(zhuǎn)，那 中對應(yīng)第r位的格雷碼剛和等于 中第2ⁿ-r-1位的格雷碼。最后，在g(r)前添一個(gè)1，正好相當(dāng)于g(r)+(1000…000)₂，共n個(gè)0。換成10進(jìn)制，就得到g(k) = 2ⁿ + g(2ⁿ – 1 – r )了。根據(jù)這個(gè)公式，我們可以得出一個(gè)非常有用的結(jié)論：給出整數(shù)k和它的二進(jìn)制形式(…b₂b₁b₀)₂，以及第k位的格雷碼g(k)的二進(jìn)制形式(…a₂a₁a₀)₂，我們可以用數(shù)學(xué)歸納法證明下面的關(guān)系：

這個(gè) 表示位運(yùn)算中的異或運(yùn)算。也就是說，只有當(dāng)兩個(gè)位不一樣時(shí)他們異或的結(jié)果為1。不然就為0。比如說，當(dāng)k ＝ 3651時(shí)，它的二進(jìn)制形式是(111001000011)₂。那第k位的格雷碼g(k)就是 k ^ (k >> 1) = 2402 = (100101100010)₂。證明其實(shí)也不難，利用公式g(k) = 2ⁿ + g(2ⁿ – 1 – r )對n做歸納就行。有興趣的老大們可以自己去做。網(wǎng)上也有答案。

現(xiàn)在我們把 從j開始展開，看看能得到什么：

 

對等式兩邊分別求異或，我們得到

 

中間項(xiàng)都消掉了，因?yàn)?等于0， 而0在異或運(yùn)算中是identity, 也就是說任何一個(gè)值與0異或還是等于自身。這個(gè)等式看來是無窮項(xiàng)，但因?yàn)?遲早會(huì)等于0， 所以它其實(shí)是有限的，可以計(jì)算。

根據(jù)公式（5），我們得到很酷的公式：

注意這個(gè) 對應(yīng)編程里的位移運(yùn)算：k >> 1，所以實(shí)現(xiàn)起來也方便。我們立刻有了新的算法，異常簡潔：

 
defgray_g(n)
   return [] if n ==0
   return (0..((1<<n) -1)).collect{|k|sprintf(“%0#{n}b”, (k ^ (k>>1)))}
end
 

上述程序無非是說，從0循環(huán)到2ⁿ, 對每個(gè)循環(huán)k， g(k) = k ^ (k >> 1)。夠簡潔吧？唯一的問題是，這個(gè)方法還是不夠高效。每次循環(huán)，我們都要對k做位移。而位移的時(shí)間和k的長度成正比。循環(huán)2ⁿ次是很大的開銷，我們自然希望每次循環(huán)的計(jì)算量越小越好。

同理，公式（6）可以導(dǎo)出很酷的反向公式。于是我們可以求出任意格雷碼的位置：

如果有些老大對這種寫法不習(xí)慣，下面的等價(jià)寫法也許清楚點(diǎn)：

對應(yīng)的代碼也很直觀：

def gray_pos(gray_code)
 pos = g = gray_code.to_i(2)
 while g > 0 
    g >>= 1
    pos ^= g
 end



 return pos
end

其實(shí)格雷碼的原理早已隱含在九連環(huán)的解法里。九連環(huán)的傳統(tǒng)解法對應(yīng)一種頗為高效的格雷碼生成代碼。關(guān)于九連環(huán)的知識(shí)，可以到這里或者這里去了解。俺就不羅嗦了。從推導(dǎo)算法的角度出發(fā)，我們只需要知道玩兒九連環(huán)的兩條規(guī)則（引自上面鏈接的文章）：

a)： “第1號(hào)環(huán)隨時(shí)可自由上下”

b)： “其他環(huán)當(dāng)且僅當(dāng)它前面僅有與它相鄰的一個(gè)環(huán)在上面時(shí)可自由上下。”

（從TAOCP截的圖）

 

基于這兩條規(guī)則，我們可以把九連環(huán)上每個(gè)環(huán)的狀態(tài)用2進(jìn)制數(shù)表示。環(huán)在杠上，對應(yīng)的數(shù)字為1，環(huán)在杠下，對應(yīng)的數(shù)字為0。比如上圖的，從左向右數(shù)，對應(yīng)的數(shù)字是(1011000)₂。注意第二個(gè)環(huán)沒有套在杠上。這樣的話，解環(huán)對應(yīng)于把(111…11)₂變成(000…00)₂。而套環(huán)對應(yīng)于把(000…00)₂變成(111…11)₂。因?yàn)槊看巫疃嘧儎?dòng)一個(gè)環(huán)，解環(huán)或套環(huán)環(huán)的過程相當(dāng)于生成格雷碼全序列。

 

1872年一個(gè)名叫Louis Gros的法國官員證明了如果一個(gè)九連環(huán)的狀態(tài)為(a_n-1…a₀)₂， 而我們按上面的公式（6）定義一個(gè)二進(jìn)制數(shù)k = (b_n-1, … , b₀)₂, 那么我們可以剛好用k步解除該九連環(huán)。從這個(gè)意義說，Gros老大才是格雷碼的真正發(fā)明人。

 

我們用解環(huán)來說明格雷碼的生成過程。只要九連環(huán)的狀態(tài)不是(000…00)₂或(100…00)₂, 那我們只可能執(zhí)行規(guī)則a)或者b)，而且只有其中一步可以讓我們靠近答案。規(guī)則a)把環(huán)取下時(shí)，相當(dāng)于最末一環(huán)的狀態(tài)從1變成0， 而套環(huán)相當(dāng)于把0變成1。也就是說 。參考公式(6)，這相當(dāng)于把把k變成 ，因?yàn)橹挥衚₀變了。顯然我們希望當(dāng)k的最后一位是1，也就是當(dāng)k為奇數(shù)時(shí)按規(guī)則a)執(zhí)行。這樣k變成k-1，離我們的目標(biāo)近了一步。另外一方面，根據(jù)規(guī)則b)，只有形為(…x100…00)₂的九連環(huán)可以移動(dòng)x代表的那個(gè)環(huán)。換句話說，如果一個(gè)長度為n的九連環(huán)里某個(gè)環(huán)所在位置以(10^j-1)₂結(jié)尾（這里(10^j-1)₂表示一個(gè)二進(jìn)制數(shù)，第一位是1，后面跟了j – 1個(gè)0）, 1 <= j < n, 則該環(huán)可以移動(dòng)。該環(huán)對應(yīng)a_j+1, 所以移動(dòng)后該環(huán)的狀態(tài)變成 。根據(jù)公式(6)，我們知道b_j, b_j-1，… , b₀, 都包含a_j+1項(xiàng)。所以說移動(dòng)該環(huán)后，k變成了 。舉個(gè)例子哈。上面九連環(huán)圖里從右數(shù)第3個(gè)環(huán)可以被解下。用數(shù)字來表達(dá)，就是(1011000)₂可以變成(1001000)₂。具體到右數(shù)第三左數(shù)第5個(gè)環(huán)，我們可以說a₄從1變成0。解環(huán)前k等于gray_pos(0b101100) = 55=(110111)₂, 解下環(huán)后k變成了 = gray_pos(0b100100) = 56 = (111000)₂。同執(zhí)行規(guī)則a)一樣，我們希望執(zhí)行規(guī)則b)后k變?。?應(yīng)該等于k – 1。要達(dá)到這個(gè)目標(biāo)，k必須是2^j的倍數(shù)，但不能是2^j+1的倍數(shù)。這是因?yàn)樾稳?xxx…10^j)₂的數(shù)才是2^j的倍數(shù)。它和2^j+1-1異或后，才能等于(xxx…01^j )₂，也就是k-1。我們可以把j和k的關(guān)系表達(dá)為：

這里的函數(shù) 叫作ruler function，有興趣的老大們可以參見這里的第13頁，印張第8頁，公式32到45。那節(jié)專講位運(yùn)算的技巧，可以和IBM某編譯器牛人出的Hacker‘s Delight以及這個(gè)網(wǎng)頁一塊兒看。做嵌入式的老大和雅好底層優(yōu)化的老大們應(yīng)該可以獲益不少。不過這里俺就不跑題了。我們只需要知道 返回k靠右連續(xù)0的個(gè)數(shù)。比如說 。從九連環(huán)可以自由移動(dòng)的那頭給環(huán)的移動(dòng)次序編號(hào)：0, 1, 2, …, ， 那把環(huán)的狀態(tài)從00000…0變成1111…11的移動(dòng)順序就是 。那對應(yīng)的算法也就很直觀了：設(shè)定長度為n的序列，該算法從(0, 0, 0…, 0)開始，逐次訪問每個(gè)組合：(a_n-1, …, a₀)₂。每一步只改變一位，相當(dāng)于移動(dòng)一個(gè)環(huán)。對每一步i,  移動(dòng)對應(yīng)的環(huán)相當(dāng)于找到 對應(yīng)的環(huán)，然后對它的值求補(bǔ)（異或）。我們也不需要每次通過求異或判斷奇偶來決定執(zhí)行規(guī)則a)還是規(guī)則b)：維護(hù)一個(gè)奇偶值，parity就行了：