排列组合算法1：生成全部有序列b

对推导不感兴趣的老大们可以通过搜索”def”直接跳到代码实现部分。不过有闲心还是瞧瞧推导过程的好。我们可以看见好的算法并非无迹可寻，完全依赖某位大牛的灵光闪现，而是通过观察、归纳、试验、迭代改进，逐步雕琢而成。另外，我们时常感叹，要是有时间学习算法就好了。要是有时间仔细读读TAOCP就好了。其实呢，读TAOCP也不是抢鸡蛋的大事。想读了，就备好纸笔，调出趁手的编辑器，打开书，翻到自己感兴趣的章节。遇到公式就推一下。遇到算法就实现 一下。遇到概念就举几个例子印证一下。遇到难解之处就和Google勾兑一下（不要忘了Google Group，真正的技术宝藏）。至于一次读多久，钻多深，施主随喜。再说从俺写的这个系列可以看出，TAOCP不少章节也就需要高中知识，到数列为止。本来是很美好的事。不必正襟危坐。不必如临大敌。不必把自己逼得太紧。你会发现花的时间不多，收获却不小。

上次说到利用递归定义生成格雷码。为了方便，我们把公式重新列一下：

其实我们也可以用递推公式定义格雷码:，明确地给出格雷码表里每一位格雷码的表达式： 。这里的g(k)表示在格雷码表里排在第k位的格雷码。其实，因为 以 开头，格雷码的无限序列是所有非负整数的某个排列：

如果我们把每个格雷码看作前面可以填充零的二进制整数，那长度为N的格雷码序列 包含公式(4)中最前面的2ⁿ个整数。只不过每个整数前可能填充0，使之长度为N。再把整数转换成字符串，就生成了相应的格雷码。比如说当N＝3时，第二位格雷码是001，相当于在公式(4)里的第二个整数(1)₂前面补上两个0后将其转换为字符串，使得该字符串的长度等于3。

当k = 2ⁿ + r 且 时，我们可以从公式(3)得出g(k) = 2ⁿ + g(2ⁿ – 1 – r )。这个结论的推导也挺容易：既然k > 2ⁿ, 那么我们知道g(k)一定在 里面。既然 表示将 反转，那 中对应第r位的格雷码刚和等于 中第2ⁿ-r-1位的格雷码。最后，在g(r)前添一个1，正好相当于g(r)+(1000…000)₂，共n个0。换成10进制，就得到g(k) = 2ⁿ + g(2ⁿ – 1 – r )了。根据这个公式，我们可以得出一个非常有用的结论：给出整数k和它的二进制形式(…b₂b₁b₀)₂，以及第k位的格雷码g(k)的二进制形式(…a₂a₁a₀)₂，我们可以用数学归纳法证明下面的关系：

这个 表示位运算中的异或运算。也就是说，只有当两个位不一样时他们异或的结果为1。不然就为0。比如说，当k ＝ 3651时，它的二进制形式是(111001000011)₂。那第k位的格雷码g(k)就是 k ^ (k >> 1) = 2402 = (100101100010)₂。证明其实也不难，利用公式g(k) = 2ⁿ + g(2ⁿ – 1 – r )对n做归纳就行。有兴趣的老大们可以自己去做。网上也有答案。

现在我们把 从j开始展开，看看能得到什么：

对等式两边分别求异或，我们得到

中间项都消掉了，因为 等于0， 而0在异或运算中是identity, 也就是说任何一个值与0异或还是等于自身。这个等式看来是无穷项，但因为 迟早会等于0， 所以它其实是有限的，可以计算。

根据公式（5），我们得到很酷的公式：

注意这个 对应编程里的位移运算：k >> 1，所以实现起来也方便。我们立刻有了新的算法，异常简洁：

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

上述程序无非是说，从0循环到2ⁿ, 对每个循环k， g(k) = k ^ (k >> 1)。够简洁吧？唯一的问题是，这个方法还是不够高效。每次循环，我们都要对k做位移。而位移的时间和k的长度成正比。循环2ⁿ次是很大的开销，我们自然希望每次循环的计算量越小越好。

同理，公式（6）可以导出很酷的反向公式。于是我们可以求出任意格雷码的位置：

如果有些老大对这种写法不习惯，下面的等价写法也许清楚点：

对应的代码也很直观：

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



return pos
end

其实格雷码的原理早已隐含在九连环的解法里。九连环的传统解法对应一种颇为高效的格雷码生成代码。关于九连环的知识，可以到这里或者这里去了解。俺就不罗嗦了。从推导算法的角度出发，我们只需要知道玩儿九连环的两条规则（引自上面链接的文章）：

a)： “第1号环随时可自由上下”

b)： “其他环当且仅当它前面仅有与它相邻的一个环在上面时可自由上下。”

（从TAOCP截的图）

基于这两条规则，我们可以把九连环上每个环的状态用2进制数表示。环在杠上，对应的数字为1，环在杠下，对应的数字为0。比如上图的，从左向右数，对应的数字是(1011000)₂。注意第二个环没有套在杠上。这样的话，解环对应于把(111…11)₂变成(000…00)₂。而套环对应于把(000…00)₂变成(111…11)₂。因为每次最多变动一个环，解环或套环环的过程相当于生成格雷码全序列。

1872年一个名叫Louis Gros的法国官员证明了如果一个九连环的状态为(a_n-1…a₀)₂， 而我们按上面的公式（6）定义一个二进制数k = (b_n-1, … , b₀)₂, 那么我们可以刚好用k步解除该九连环。从这个意义说，Gros老大才是格雷码的真正发明人。

我们用解环来说明格雷码的生成过程。只要九连环的状态不是(000…00)₂或(100…00)₂, 那我们只可能执行规则a)或者b)，而且只有其中一步可以让我们靠近答案。规则a)把环取下时，相当于最末一环的状态从1变成0， 而套环相当于把0变成1。也就是说 。参考公式(6)，这相当于把把k变成 ，因为只有k₀变了。显然我们希望当k的最后一位是1，也就是当k为奇数时按规则a)执行。这样k变成k-1，离我们的目标近了一步。另外一方面，根据规则b)，只有形为(…x100…00)₂的九连环可以移动x代表的那个环。换句话说，如果一个长度为n的九连环里某个环所在位置以(10^j-1)₂结尾（这里(10^j-1)₂表示一个二进制数，第一位是1，后面跟了j – 1个0）, 1 <= j < n, 则该环可以移动。该环对应a_j+1, 所以移动后该环的状态变成 。根据公式(6)，我们知道b_j, b_j-1，… , b₀, 都包含a_j+1项。所以说移动该环后，k变成了 。举个例子哈。上面九连环图里从右数第3个环可以被解下。用数字来表达，就是(1011000)₂可以变成(1001000)₂。具体到右数第三左数第5个环，我们可以说a₄从1变成0。解环前k等于gray_pos(0b101100) = 55=(110111)₂, 解下环后k变成了 = gray_pos(0b100100) = 56 = (111000)₂。同执行规则a)一样，我们希望执行规则b)后k变小： 应该等于k – 1。要达到这个目标，k必须是2^j的倍数，但不能是2^j+1的倍数。这是因为形如(xxx…10^j)₂的数才是2^j的倍数。它和2^j+1-1异或后，才能等于(xxx…01^j )₂，也就是k-1。我们可以把j和k的关系表达为：

这里的函数 叫作ruler function，有兴趣的老大们可以参见这里的第13页，印张第8页，公式32到45。那节专讲位运算的技巧，可以和IBM某编译器牛人出的Hacker's Delight以及这个网页一块儿看。做嵌入式的老大和雅好底层优化的老大们应该可以获益不少。不过这里俺就不跑题了。我们只需要知道 返回k靠右连续0的个数。比如说 。从九连环可以自由移动的那头给环的移动次序编号：0, 1, 2, …, ， 那把环的状态从00000…0变成1111…11的移动顺序就是 。那对应的算法也就很直观了：设定长度为n的序列，该算法从(0, 0, 0…, 0)开始，逐次访问每个组合：(a_n-1, …, a₀)₂。每一步只改变一位，相当于移动一个环。对每一步i, 移动对应的环相当于找到 对应的环，然后对它的值求补（异或）。我们也不需要每次通过求异或判断奇偶来决定执行规则a)还是规则b)：维护一个奇偶值，parity就行了：

32: def alg_g(n)
33: step = Array.new(n, 0)
34: result = []
35: parity = 0
36: 
37: loop do
38: result << step.join
39: parity = 1 - parity
40: 
41: if parity == 1
42: j = 0
43: else
44: 0.upto(n-1) do |i|
45: if step[i] == 1
46: j = i+1
47: break
48: end
49: end
50: end
51: 
52: return result.reverse if j == n
53: 
54: step[j] = 1 - step[j]
55: end
56: end

这个奇偶位很有点意思。当我们要计算求和公式

或者

且计算结果只依赖于二进制字串的奇偶性或者某个子集里的元素个数的时候，这个公式就变得很方便了。而且这个奇偶位也让上面的算法变得高效：没有它的话，决定到底执行规则a）还是规则b）就不容易了。

这个算法最精当的地方在于第54行。我们只需要对一个bit做出改动。不过呢，对每一个生成的格雷码，我们有可能执行第44到48行的内循环。当我们要执行2ⁿ次外循环时，这个开销还是大了点。所以我们接下来要介绍除去Gideon Ehrlich在1973年提出的方法，消去内循环，并从中学到新的设计算法解决问题的手段。

评论

1 楼 nothingtalk 2011-02-27  

博主，您好。
“所以我们接下来要介绍除去Gideon Ehrlich在1973年提出的方法，消去内循环，并从中学到新的设计算法解决问题的手段。
”
说的文章怎么找不到呢？不会是册了吧？