排列组合算法1:生成全部有序列b
来源:百度文库 编辑:神马文学网 时间:2024/10/06 23:23:48
对推导不感兴趣的老大们可以通过搜索”def”直接跳到代码实现部分。不过有闲心还是瞧瞧推导过程的好。我们可以看见好的算法并非无迹可寻,完全依赖某位大牛的灵光闪现,而是通过观察、归纳、试验、迭代改进,逐步雕琢而成。另外,我们时常感叹,要是有时间学习算法就好了。要是有时间仔细读读TAOCP就好了。其实呢,读TAOCP也不是抢鸡蛋的大事。想读了,就备好纸笔,调出趁手的编辑器,打开书,翻到自己感兴趣的章节。遇到公式就推一下。遇到算法就实现一下。遇到概念就举几个例子印证一下。遇到难解之处就和Google勾兑一下(不要忘了Google Group,真正的技术宝藏)。至于一次读多久,钻多深,施主随喜。再说从俺写的这个系列可以看出,TAOCP不少章节也就需要高中知识,到数列为止。本来是很美好的事。不必正襟危坐。不必如临大敌。不必把自己逼得太紧。你会发现花的时间不多,收获却不小。
上次说到利用递归定义生成格雷码。为了方便,我们把公式重新列一下:
其实我们也可以用递推公式定义格雷码:,明确地给出格雷码表里每一位格雷码的表达式:
如果我们把每个格雷码看作前面可以填充零的二进制整数,那长度为N的格雷码序列
当k = 2n + r 且
这个
现在我们把
对等式两边分别求异或,我们得到
中间项都消掉了,因为
根据公式(5),我们得到很酷的公式:
注意这个
defgray_g(n)
return [] if n ==0
return (0..((1<
end
上述程序无非是说,从0循环到2n, 对每个循环k, g(k) = k ^ (k >> 1)。够简洁吧?唯一的问题是,这个方法还是不够高效。每次循环,我们都要对k做位移。而位移的时间和k的长度成正比。循环2n次是很大的开销,我们自然希望每次循环的计算量越小越好。
同理,公式(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): “其他环当且仅当它前面仅有与它相邻的一个环在上面时可自由上下。”
基于这两条规则,我们可以把九连环上每个环的状态用2进制数表示。环在杠上,对应的数字为1,环在杠下,对应的数字为0。比如上图的,从左向右数,对应的数字是(1011000)2。注意第二个环没有套在杠上。这样的话,解环对应于把(111…11)2变成(000…00)2。而套环对应于把(000…00)2变成(111…11)2。因为每次最多变动一个环,解环或套环环的过程相当于生成格雷码全序列。
1872年一个名叫Louis Gros的法国官员证明了如果一个九连环的状态为(an-1…a0)2, 而我们按上面的公式(6)定义一个二进制数k = (bn-1, … , b0)2, 那么我们可以刚好用k步解除该九连环。从这个意义说,Gros老大才是格雷码的真正发明人。
我们用解环来说明格雷码的生成过程。只要九连环的状态不是(000…00)2或(100…00)2, 那我们只可能执行规则a)或者b),而且只有其中一步可以让我们靠近答案。规则a)把环取下时,相当于最末一环的状态从1变成0, 而套环相当于把0变成1。也就是说
这里的函数
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行的内循环。当我们要执行2n次外循环时,这个开销还是大了点。所以我们接下来要介绍除去Gideon Ehrlich在1973年提出的方法,消去内循环,并从中学到新的设计算法解决问题的手段。
Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=1558391
[收藏到我的网摘] g9发表于 2007年04月10日 04:16:00