守夜人
Got 24 items. ['1234', '2134', '2314', '2341', '1324', '3124', '3214', '3241', '1342', '3142', '3412', '3421', '1243', '2143', '2413', '2431', '1423', '4123', '4213', '4231', '1432', '4132', '4312', '4321']
上面就是 permute7.py 产生的四位数字排列结果, 你细心地反覆观看, 终於看出了一些端倪: 其实所产生的排列是有一种对称性的, 第一个和最后一个是完全次序相反的, 而第二个又和倒数第二个完全相反. 利用这些对称性, 也许你可以把计算时间打个对折哟. 而你研究了一下程式的实现方法后你发现只要改一行! 就可以实现这样的功能: 就是第一行 seqn = [ seq.pop() ] 改成 seqn = [ seq.pop()+seq.pop() ]. 这样你就实现了只产生其中一半的排列, 尔后你只要把这个列表中的元素都掉个就完成了整个排列. 程式如下
1 # permute7.py
2 def permute(seq):
3 seqn = [ seq.pop()+seq.pop() ]
4 while seq:
5 newseq = []
6 new = seq.pop()
7 #print "seq:",seq,'seqn', seqn ,'new', new
8 for i in range(len(seqn)):
9 item = seqn[i]
10 for j in range(len(item)+1):
11 newseq.append(''.join([item[:j],new,item[j:]]))
12 seqn = newseq
13 #print 'newseq',newseq
14 return seqn
15
16 import sys, calc
17 seq = list(sys.argv[1])
18 where = int(sys.argv[2])
19 thelist = permute(seq)
20 print 'Got', len(thelist), 'items.'
21 print thelist
22 # 这个等一下再探讨
23 #calc.calc2(thelist, where)
测试数据表示果然这个改良了的程式要比原来快了刚好一倍. 这次应该足够了. 但是要得到整个排列的话要把这半个列表重抄一次而且每个元素都要反过来: "1234" -> "4321". 但是在 Python 之中的字串并没有反序的函数, 因此你必须先把字串变成列表, 再反过来, 然而 list.reverse() 这个函数偏偏很讨厌的不会传回任何值 (因为它是 in-place 的缘故), 所以你要用 i = list(item); i.reverse; i = ''.join(i); 这个复杂的方法. 你想了想, 这个做法大概会把原来只做一半排列所省下来的时间都浪费掉了. 你思考半天, 终於决定重写 calc.py 部份以便直接利用已知的半个列表.
1 # calc.py
2 def calc(seq, where):
3 maximum, max_item = 0, []
4 for i in seq:
5 product = int(i[:where]) * int(i[where:])
6 if product > maximum:
7 maximum, max_item = product, i
8 elif product == maximum:
9 max_item += ','+i
10 print "Maximum at", max_item, ",product", maximum
11
12 def calc2(seq, where):
13 maximum, max_item = 0, []
14 for i in seq:
15 product = int(i[:where]) * int(i[where:])
16 if product > maximum:
17 maximum, max_item = product, i
18 elif product == maximum:
19 max_item += ','+i
20 rev = list(i)
21 rev.reverse()
22 i = ''.join(rev)
23 product = int(i[:where]) * int(i[where:])
24 if product > maximum:
25 maximum, max_item = product, i
26 elif product == maximum:
27 max_item += ','+i
28 print "Maximum at", max_item, ",product", maximum
当然你保留了以前的函数 calc 而只是新加一个专门给 permute7.py 调用的 calc2 函数. 你试了一下速度, 成功了比 permute6.py 快了一丁点. 虽然只是这一点儿点儿, 你也觉得快活无比. 因为又一次, 你为一个大家都觉得好的方法做出了改良.
虽然你知道在这个阶段如果你把 calc.py 整合到排列产生器中也许会得更好的提速效果, 但你觉得现在这样已经可以很多人都认同你的能力了. 而且能把一个高效的排列产生器独开来也许是聪明的做法, 因为将来你一定会再用它的. 你看了一下所有的程式, 从 permute1.py 到 permute7.py, 再做了一次速度的检定. 反正是最后一次了, 干脆做个大的吧.
$ time python permute2.py 123456789 5 Got 362880 items. Maximum at 875319642 ,product 843973902 real 0m46.478s user 0m46.020s sys 0m0.430s $ time python permute3.py 123456789 5 Got 362880 items. Maximum at 875319642 ,product 843973902 real 0m38.997s user 0m38.600s sys 0m0.400s $ time python permute4.py 123456789 5 Got 362880 items. Maximum at 875319642 ,product 843973902 real 0m33.845s user 0m33.460s sys 0m0.380s $ time python permute5.py 123456789 5 Got 362880 items. Maximum at 875319642 ,product 843973902 real 0m10.681s user 0m10.530s sys 0m0.150s $ time python permute6.py 123456789 5 Got 362880 items. Maximum at 875319642 ,product 843973902 real 0m8.279s user 0m8.110s sys 0m0.170s $ time cpython permute7.py 123456789 5 Got 181440 items. Maximum at 875319642 ,product 843973902 real 0m7.827s user 0m7.650s sys 0m0.180s
嗯, 很不错. 最快的要比原先快上近七倍呢! 於是你打算明天一有空便把这个最好的公式贴到网上去, 让更多人分享. 你很放心地去睡觉了.
但是不知为了什么, 你总觉得有些事烦扰著你, 还有什么不妥的地方呢? 你实在想不到了, 迷迷糊糊地抱著迷惑不安的心情入梦.
终於你忍不住爬了起床, 再一次回到电脑屏幕前. 你想到了一个致命的问题, 对於很大很大的排列, permute7.py 还是会尝试一下子把所有的排列都做出来, 不用多久电脑资源就会被耗光的. 你也许要另想一个方法, 每次只做一个排列. 但你是否可以把所有的排列用 1, 2, 3, 4 的方法数出来呢?
你看著教科书上的那幅图画, 这样的树状结构应该有办法的, 你对自己说.
慢慢读著书上的文字. 设想有 n 个数字, 先取第一个数字. 再取第二个数字, 第二个数可以放在第一个数的左或右面, 就是有 0, 1 两个选择. 再取第三个数, 放到前面选好的两个数字中, 可以放在最左, 中间, 最右, 就是有 0, 1, 2 三个选择. 嗯, 很自然吗. 忽然你想到了二进位, 八进位那些数系转换关系. "我可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 化表放第三个数字的三个位子, 然后百位数是四进位, 千位数是五进位的, 依以类推." 没错, 这样设计的话, 如果 0 表示放於最左面的话, 则 "2021" 这个数就代表了排列五个元素 (abcde), 取一个 a, 然后第二个 b 放在 a 的右面成 ab, 取 c 放到最右面成为 abc, 取 d 放到最左面成 dabc; 最后 e 放到中间去成为 daebc. 至於 "2021" 这个特别的设计的数可以用 ..+ x*4 + y*3 + z*2 这样的计算来映对到自然数的数列上去.
没错了, 如求 4 个数的 4! = 24 个排列, 第 18 个排列可以这样求得, 18 除 2, 余数是 0, 所以第二个数放在第一个数的左面; 然后商 9 再除 3, 余数 0, 所以第三个数於在头两个数的最左; 最后 3 除以 4, 余数是 3, 因此第四个数要放在前三个数的第 4 个空位, 也就是最右面. 利用这个方法, 你就不必先求出整个排列才能开始计算. 尽管这好像牺牲了时间, 但省下了大量的空间. 你完全可以算出 1000 个数的最大排列方法, 纵使那可能要用去几个月的运算. 你更高兴的是用这个方法, 你可以把整个计算拆开成为一个一个的部份: 譬如说求 10! = 3628800 个排列, 你大可以把 1 到 1000000 让一部电脑做, 1000001 到 2000001 让另一部来做 ... 大家的工作并不重覆, 这等於实现并行运算了! 啊哈! 妙极了!
忽然你灵光一闪, 对了, 这个不正是 permute4.py 的算法吗! 你昨天还久思不得其解呢, 现在你已经完全明白了. 呜, 虽然这么好的算法原来不是你原创的, 但是你仍然异常兴奋. 因为你的思路竟和那些大牛们互相吻合. 你渐渐记起了当你还在玩 DOS 游戏机的年代, 曾有个古怪的人向你吹嘘过某个电脑扑克游戏中用了一个威力很大的洗牌法, 多么的快而且公平, 不必怕黑客们用已知的随机数表来出千. 现在你猜到了, 那个算法很可能就是眼下这一个了. 有 52 张牌, 如果要预先算出 52! 个排列才能洗牌可真要命呢.
你觉得舒服多了, 你整理了一下程式, 打算把结果告诉大家. 然而刚才的不安感又重新来袭. 你再看了一次最后也应该是最棒的程式, 心中安慰自己道: "千万不要跌进低等程式员的的陷阱, 他们疯也似的不断追求, 郤从来不知道自己的目标, 也不知道什么才是好. 完美的设计不在于你无 法添加新的功能, 完美的设计是再也不能精简现有的功能." 你觉得 permute7.py 已迫近了这一个 极限. 但你内心深处并没有因此而舒坦开来, 一种悬空的感觉自足下升起. 也许是你太累了, 于是 者你决定闭目养神数分钟再开始上网, 可惜你很快地迷迷糊糊地进入了梦境.
待续...