一切从游戏开始

1. 一切从游戏开始: 2. 第二天: 3. 守夜人: 4. 终篇: 5. 课后检讨: l 故事虚构, 是从一个真的游戏再综合新闻组的内容而来. 缘起: 这是一个晴朗的星期六下午, 你悠闲地在网上浏览. 忽然间你看到一个留言板上的小游戏. 它 很简单, 问是: 把五个数字 56789, 放到 {{{[][][] * [][], 令结果最大. 你最先对自己说: "这有什么难, 把最大的放到最大位数那里就行了." 你再心算了一下, 也许 不对. 每个结果要看其他位置上放了什么数才行. 你开始觉得有些兴趣了, 反正你正在学一种 好玩的编程语言, 何不练习一下呢? 於是你开出你心爱的 Python, 开始思考: "其实我要的是一个程式, 我给它各种数字的组合, 然后它自动帮我找出最大的一个. 如果我传入 1,1,1,1,1 和 1,1,1,1,2, 它会知道要算 111 * 11 和 111 * 12, 求出较大的是 111 * 12 并输出这个组合以及其乘积. 这个程式并不难嘛." 你试了一下, 一切从游戏开始 一切从游戏开始: 1 # calc.py 2 def calc(seq): 3 maximum = 0 4 max_item = [] 5 for i in seq: 6 product = (i[0]*100 + i[1]*10 + i[2]) * (i[3]*10 + i[4]) 7 if product > maximum: 8 maximum = product 9 max_item = i 10 elif product == maximum: 11 max_item += ','+i 12 return max_item, maximum 13 14 seq = [ [5,6,7,8,9], [5,6,7,9,8] ] 15 max_item, maximum = calc(seq) 16 print "Maximum at", max_item, ",product", maximum $python calc.py Maximum at [5, 6, 7, 9, 8] ,product 90160 Page 1 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 没问题. 现在你只要给出所有的排列即可. 你打了几行, 觉得 [5,6,8,7,9] 这样打太辛苦了, 而且用 i[0]*100 + i[1]*10 ... 的好像太难看了, 因此你有必要做一次修改. 好, 用字 串吧. "56789", 这样输入时较方便, 而且 int("567") * int("89") 要好看得多, 也应该快 些. 另外你也把程式改得更短, 看起来像是个有经验的人所写. 嗯, 好些了. 那句 if __name__ == "__main__" 是为了将来你把 calc.py 做为模组来用时而 设的. 在别的程式中用 import calc 的话那几行就不会运行了. 现在你可以随自己的意来解更普遍的问题, 比如 123 放在 []*[][], 或是 1234567 放在 [][] [][]*[][][] 这样的问法. 现在你开始输入排列了. "56789", "56798", "56879", "56897", .......... 没多久你又觉得自己太愚蠢了, 为什么不叫电脑程式自动产生这些无聊的排列呢? 56789 一共有 5! 也就是 120 种排列方法呢! 如果你想算 123456789 的话, 用手输入可能要 用去一生的时间!! 於是你开始想如何产生排列的算法了. 用循环就可以了, 不过循环会产生重覆的组合, 譬如 555*55. 但我们可以加些条件式进去把重覆项拿走. 於是你有了第一个程式解. 你小心地记著用 ''.join() 的方法产生字串要比用 a+b+c+d 快, 同时也认为用 import calc 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 if __name__ == "__main__": 13 seq = [ "56789", "56798" ] 14 where = 3 15 calc(seq,where) 1 #permute1.py 2 def permute(seq): 3 result = [] 4 for a in seq: 5 for b in seq: 6 for c in seq: 7 for d in seq: 8 for e in seq: 9 if a!=b and a!=c and a!=d and a!=e and \ 10 b!=c and b!=d and b!=e and \ 11 c!=d and c!=e and d!=e: 12 result.append(''.join([a,b,c,d,e])) 13 return result 14 15 seq = list("56789") 16 where = 3 17 thelist = permute(seq) 18 import calc 19 calc.calc(thelist,where) Page 2 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 的方式会让你更容易为不同的地方做些速度的微调. 你开始运行程式了: 你成功了. 啊哈, 你认为可以贴到留言板上去领赏了. 经过一些考虑后, 你觉得还是要做到更 普遍的功能, 就是让用户输入排列多少个数字, 怎样分割. 研究了一下程式, 你觉得用循环好 像无法达到要求, 因为你事前并不知道要排多少个数字, 因此你不知道要写多少个循环才够. 面对这种情况, 你好像只能用递归的方法了. 你知道如何求得, 例如, 5 个数字的排列: 先挑一个数, 有五种选择; 当选定了一个数之后挑 第二个数时只剩下四个选择, 依此类推. 因此五个数共有 5*4*3*2*1 共 120 个排列. 当你面 对 "56789" 这五个数的排列问题时, 你先挑出一个数, 例如 6, 那剩下的便是一个四个数字的 排列问题了. 就是说, 56789 的排列可以简化 (或是简单复杂化:p) 成字头为 5 的所有排列加 上字头为 6 的所有排列加字头为 7 的所有排列加字头为 8 的所有排列再加字头为 9 的所有 排列. 想通了这点, 你决定用递归来写程式, 先依次在 56789 中选出 5, 然后把剩下的 6789 当做是一个新的求四位数排列的问题再次调用函数, 以得到所有以 5 为字头的排列; 再 选出 6, 剩下的 5789 调用函数. 而每次求 6789 或是 5789 的排列时再把它简化成另一个求 3 个数字的排列问题, 直到要求的排列只剩下一个数. 以下就是你的函数, 不过你还不知道它到底是不是正确的, 因为写递归函数很易出错, 因此你 要先试一下. 你运行后得到以下的结果: 看来是正确的. 但有没有办法再快一些呢? 你想了半天, 终於发现其实你不必等到 l = 1 的时 候才有所动作, 你可以在 l = 2 的时候就干些事了. 因为你知道 l = 2 的话, 排列一定是 [ [0,1], [1,0] ] 的, 这样你起码可以用些力气帮电脑一把. 当然如果你把 l = 3 的排列也 写出来更好, 但写到 l = 4 或以上大可不必了. 这种帮它一下的做法在程式优化中的学名是 %python permute1.py Maxmum at 87596 ,product 84000 1 #permute2.py 2 def permute(seq): 3 l = len(seq) 4 if l == 1: 5 return [seq] 6 else: 7 res=[] 8 for i in range(len(seq)): 9 rest = seq[:i] + seq[i+1:] 10 for x in permute(rest): 11 res.append(seq[i:i+1] + x) 12 return res 13 14 seq = list("1234") 15 thelist = permute(seq) 16 thelist = [ ''.join(x) for x in thelist ] 17 print thelist $ python permute2.py ['1234', '1243', '1324', '1342', '1423', '1432', '2134', '2143', '2314', '2341', '2413', '2431', '3124', '3142', '3214', '3241', '3412', '3421', '4123', '4132', '4213', '4231', '4312', '4321'] Page 3 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... unroll, 你隐约记得是学过的. 好, 现在你有另一个程式了. 现在你可以正式测试了. 你把 permute3.py 改了一下, 以便可以从命令行取得数字以及分割方 法. 程式变成下面的样子, 同时你也对 permute2.py 做了相同的修改. 你开始试行了. 用 time 方式来看程式到底运行了多长时间吧. 1 #permute3.py 2 def permute(seq): 3 l = len(seq) 4 if l <= 2: 5 if l == 2: 6 return [ seq, [seq[1], seq[0]] ] 7 else: 8 return [seq] 9 else: 10 res=[] 11 for i in range(len(seq)): 12 rest = seq[:i] + seq[i+1:] 13 for x in permute(rest): 14 res.append(seq[i:i+1] + x) 15 return res 16 17 seq = list("12345") 18 thelist = permute(seq) 19 thelist = [ ''.join(x) for x in thelist ] 20 print thelist 1 #permute3.py 2 def permute(seq): 3 l = len(seq) 4 if l <= 2: 5 if l == 2: 6 return [ seq, [seq[1], seq[0]] ] 7 else: 8 return [seq] 9 else: 10 res=[] 11 for i in range(len(seq)): 12 rest = seq[:i] + seq[i+1:] 13 for x in permute(rest): 14 res.append(seq[i:i+1] + x) 15 return res 16 17 import sys, calc 18 seq = list(sys.argv[1]) 19 where = int(sys.argv[2]) 20 thelist = [ ''.join(x) for x in permute(seq) ] 21 Print 'Got', len(thelist), 'items.' 22 calc.calc(thelist, where) $ time python permute2.py 56789 3 Got 120 items. Maximum at 87596 ,product 84000 real 0m0.057s Page 4 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 呵, 不错. 修改了的就是快些. 到了这个地步, 你开始觉得好奇了. 像求排列这样一个常见的 问题, 不知道别人都是怎样做的呢. 也许应该到网上去找找看, 或者有一两个已经写好的程式 片断可以抄的. 你可不想弄错一个原来己经有答案的问题. 把 permute2.py 贴上留言板或 者会令自己看起来像一个三流的程式员, 这可是你最不想见到的. 於是你在网上到处搜寻. 不过似乎都是以递归算法为主的, 直至用了一些时间, 你终於在 ASPN: 的网上程式码收集站上 看到了这一个片断: 作者声称这个算法的量级是 O(n) 的. 你觉得难以置信, 但不妨一试. 由於你理解到这个函数 每次只传回排列中的某一项, 因此你写了个小程式去验算它. 试验一下: 测试显示这个函数没问题. 但它怎样做到的呢? 你研究了一下, 每个不同的 index 值都传回唯 一的排列, 而且大过 n! 的 index 会从头来算起, divider 每次都要增加一, 列表的排法又是 按商余数来重整. 唉, 不得要领. 嗨! 管它呢. 反正能用就行了. 於是你修改 permute4.py, 加入一个新的函数求 factorial, 这样就可以调用 permute 得到所有的排列. 并进行计时. 你 用了更多的数字, 以便速度的差别更明显些. user 0m0.050s sys 0m0.000s $ time python permute3.py 56789 3 Got 120 items. Maximum at 87596 ,product 84000 real 0m0.040s user 0m0.030s sys 0m0.010s 1 # permute4.py 2 def permute(seq, index): 3 seqc = seq[:] 4 seqn = [seqc.pop()] 5 divider = 2 6 while seqc: 7 index, new_index = divmod(index,divider) 8 seqn.insert(new_index, seqc.pop()) 9 divider += 1 10 return ''.join(seqn) 1 # test.py 2 from permute4.py import permute 3 4 seq = list("1234") 5 for i in range(30): 6 print permute(seq, i), $ python test.py 1234 1243 1324 1423 1342 1432 2134 2143 3124 4123 3142 4132 2314 2413 3214 4213 3412 4312 2341 2431 3241 4231 3421 4321 1234 1243 1324 1423 1342 1432 Page 5 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 哇! 的确不是盖的. 很好, 而且现在你知道了别人不知的新答案. 就把它贴上去罢. 就在你决 定的时候按钮之际, 你到底犹豫了: "我对这个算法不是很了解, 如果别人问起的话怎样回答 呢? 这会让我像个东抄西抄的小偷呢! 不, 要不我要明白它的原理, 不然就自己做一个比它更 好的." 你觉得壮志无限. 但是现在已经很晚, 你要去睡了. 无奈你在床上反覆地思考著更好的方法, 你整个晚上都没睡 好. 待续...... 你醒来第一件事, 洗脸刷牙. 编程爱好者并不一定和终日蓬头垢面同义. 然后呢, 看看电视报 纸, 做些公益活动, 今天是礼拜天嘛. 废话少说, 终於你在电脑前坐下, 登入了你喜爱的 1 # permute4.py 2 def permute(seq, index): 3 seqc = seq[:] 4 seqn = [seqc.pop()] 5 divider = 2 6 while seqc: 7 index, new_index = divmod(index,divider) 8 seqn.insert(new_index, seqc.pop()) 9 divider += 1 10 return ''.join(seqn) 11 12 def fact(x): 13 f = 1 14 for i in range(1,x+1): 15 f *= i 16 return f 17 18 import sys, calc 19 seq = list(sys.argv[1]) 20 where = int(sys.argv[2]) 21 n = fact(len(seq)) 22 thelist = [ permute(seq, i) for i in range(n) ] 23 print 'Got', len(thelist), 'items.' 24 calc.calc(thelist, where) $ time cpython permute3.py 1234567 4 Got 5040 items. Maximum at 6531742 ,product 4846002 real 0m0.461s user 0m0.440s sys 0m0.020s $ time cpython permute4.py 1234567 4 Got 5040 items. Maximum at 6531742 ,product 4846002 real 0m0.389s user 0m0.370s sys 0m0.010s 第二天: Page 6 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... Slackware / RedHat / Redflag / Mandrake / Debian / WindowsXP / Chinese2000 / DOS / Solaris/ AIX / Unicos / OSX [作者按: 请依实际情况增删, 但千万拜托不要把 SCO 也加进 来], 这些都是 Python 能够运行的平台. 你记起你以前学到递归时听过的话: 任何递归/回溯函数都可以还原成非递归形式的. 於是你决 定用你自己的方式一试. 你默念著求排列的方法, 5 个数取一个, 剩下 4 个, 再取一个, 剩下 3 个 .... 於是你写出一个新的程式, 和最初的一个很相像: 这个程式依次创建 5, 4, 3, 2, 1 个数的列表, 每个都不包括之前被选的数字, 然后把 5 个 数合起来完成一种排列.当然, 你还有空间做 unroll. 但现在问题在於, 你对程式的要求是事 先并不知道要求多少个数字的排列, 就是你不知道要写几个 for 才够. 但现在你认为有一个好 办法: 既然 Python 是动态的, 它可以执行自己写出来的编码, 为什么不叫它自己帮自己来写 这个循环程式以完成工作呢? 你觉得这种让程式来为自己写程式的想法很科幻也很妙, 而且让 你记起了以前听到很多资深程式员爱用的 m4 宏语言. 於是你赶紧试了一个. 你认为可以用 counter0, counter1, counter2...来代替 i, j, l, m...的循环子命名法. 1 # permute5.py 2 def permute(seq): 3 result = [] 4 for i in seq: 5 seq1 = seq[:] 6 seq1.remove(i) 7 for j in seq1: 8 seq2 = seq1[:] 9 seq2.remove(j) 10 for l in seq2: 11 seq3 = seq2[:] 12 seq3.remove(l) 13 for m in seq3: 14 seq4 = seq3[:] 15 seq4.remove(m) 16 result.append(''.join([i,j,l,m,seq4[0]])) 17 return result 18 19 print permute(list("12345")) 1 # permute5.py 2 def genfunc(n): 3 head = """ 4 def permute(seq0): 5 result = [] """ 6 boiler = """ 7 for counter%i in seq%i: 8 seq%i = seq%i[:] 9 seq%i.remove(counter%i)""" 10 for i in range(1,n): 11 space = ' '*i 12 head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i) 13 temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)] 14 head = head + '\n' + space + " result.append(''.join([%s]))"%(temp) 15 return head + '\n return result\n' 16 17 import sys 18 functext = genfunc(len(sys.argv[1])) 19 print functext Page 7 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 运行一下, 看来格式是弄对了. 现在算算运行时间, 会不会好些呢? 也许会比以前更快, 也许因为要再执 行自己产生的程式而更慢, 一切都要看实际的数据才能呢! 你修改了 permute5.py 以便它能标 准化地计算时间. 你开始觉得 import calc 实在是挺聪明的设计. 20 exec(functext) 21 print dir() 22 thelist = permute(list(sys.argv[1])) 23 print 'Got', len(thelist), 'items.' sh-2.05b$ python permute5.py 12345 3 def permute(seq0): result = [] for counter1 in seq0: seq1 = seq0[:] seq1.remove(counter1) for counter2 in seq1: seq2 = seq1[:] seq2.remove(counter2) for counter3 in seq2: seq3 = seq2[:] seq3.remove(counter3) for counter4 in seq3: seq4 = seq3[:] seq4.remove(counter4) result.append(''.join([counter1,counter2,counter3,counter4,seq4[0]])) return result ['__builtins__', '__doc__', '__name__', 'calc', 'functext', 'genfunc', 'permute', 'sys'] Got 120 items. 1 # permute5.py 2 def genfunc(n): 3 head = """ 4 def permute(seq0): 5 result = [] """ 6 boiler = """ 7 for counter%i in seq%i: 8 seq%i = seq%i[:] 9 seq%i.remove(counter%i)""" 10 for i in range(1,n): 11 space = ' '*i 12 head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i) 13 temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)] 14 head = head + '\n' + space + " result.append(''.join([%s]))"%(temp) 15 return head + '\n return result\n' 16 17 import sys, calc 18 functext = genfunc(len(sys.argv[1])) 19 #print functext 20 exec(functext) 21 thelist = permute(list(sys.argv[1])) 22 print 'Got',len(thelist),'items.' 23 calc.calc(thelist,int(sys.argv[2])) Page 8 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 开始计时: 啊哈! 那个什么量级 O(n) 的也被你打败!! 你觉得它的量级其实不是 O(n), 那只是对找一整 个排列其中一个的时候才有用, 要把整个排列都算出来的话还是要回到 n! 上的. 你非常自豪. 但这也许是适当的时候提醒自己谦虚的妤处. 既然都到了这个地步了, 何不再走 多一步, 翻一下书看看, 也许你找到的方法已经早有别人发现了. 果真是这样的话, 你, 一个 无知的白痴, 到处大吹大擂自己的发明是会被笑话的. 於是你找出了封尘的电脑和数学教科书. 找到了排列组合一章, 开始细读. 终於你找到了这样 的一幅图画: 书中写到, 要产生一个排列其实可以用这样一个方法: "先选一个数 1, 然后第二个数 2 可以 放在 1 的前面或是后面. 而每一个放法都会产生一个 2 位数, 对於每一个这样的两位数, 第 三个数 3, 都可以放在它的前面, 中间, 或是最后; 如此产生一个 3 位数; 而每一个 3 位数, 第 4 位数都可以插入到这 3 个数的任何一个空位中, 如此类推. 书中还列出了一个程式范例 呢! 并声这个方法要和已知的最快的算排列的方法速度相若. 你急不可待地开始把书中的描述实现. 用 Python, 你很快又得到了一个全新的程式: $ time cpython permute5.py 1234567 4 Got 5040 items. Maximum at 6531742 ,product 4846002 real 0m0.213s user 0m0.200s sys 0m0.010s [4321] [3421] [321] < [3241] [21] < [231]... [3214] [213]... [1] < [321]... [21] < [231]... [213]... 1 # permute6.py 2 def permute(seq): 3 seqn = [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 Page 9 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 测试结果如下: 哇塞! 书中自有黄金屋咧! 想不到这个才是最快的算法. 你开始感到要击败这次的对手不是不 件容易的事, 而且现在已经很晚了, 你身心也都被疲倦所包围著. 你绝望地看著这个新的程式 码和它那美妙的结构, 作出最后的尝试: 待续... 上面就是 permute7.py 产生的四位数字排列结果, 你细心地反覆观看, 终於看出了一些端倪: 其实所产生的排列是有一种对称性的, 第一个和最后一个是完全次序相反的, 而第二个又和倒 数第二个完全相反. 利用这些对称性, 也许你可以把计算时间打个对折哟. 而你研究了一下程 式的实现方法后你发现只要改一行! 就可以实现这样的功能: 就是第一行 seqn = [ seq.pop () ] 改成 seqn = [ seq.pop()+seq.pop() ]. 这样你就实现了只产生其中一半的排列, 尔后 你只要把这个列表中的元素都掉个就完成了整个排列. 程式如下 17 seq = list(sys.argv[1]) 18 where = int(sys.argv[2]) 19 thelist = permute(seq) 20 print 'Got', len(thelist), 'items.' 21 calc.calc(thelist, where) $ time cpython permute6.py 1234567 4 Got 5040 items. Maximum at 6531742 ,product 4846002 real 0m0.167s user 0m0.150s sys 0m0.020s 守夜人: 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'] 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 Page 10 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 测试数据表示果然这个改良了的程式要比原来快了刚好一倍. 这次应该足够了. 但是要得到整 个排列的话要把这半个列表重抄一次而且每个元素都要反过来: "1234" -> "4321". 但是在 Python 之中的字串并没有反序的函数, 因此你必须先把字串变成列表, 再反过来, 然而 list.reverse() 这个函数偏偏很讨厌的不会传回任何值 (因为它是 in-place 的缘故), 所以 你要用 i = list(item); i.reverse; i = ''.join(i); 这个复杂的方法. 你想了想, 这个做 法大概会把原来只做一半排列所省下来的时间都浪费掉了. 你思考半天, 终於决定重写 calc.py 部份以便直接利用已知的半个列表. 当然你保留了以前的函数 calc 而只是新加一个专门给 permute7.py 调用的 calc2 函数. 你 试了一下速度, 成功了比 permute6.py 快了一丁点. 虽然只是这一点儿点儿, 你也觉得快活无 比. 因为又一次, 你为一个大家都觉得好的方法做出了改良. 虽然你知道在这个阶段如果你把 calc.py 整合到排列产生器中也许会得更好的提速效果, 但你 觉得现在这样已经可以很多人都认同你的能力了. 而且能把一个高效的排列产生器独开来也许 是聪明的做法, 因为将来你一定会再用它的. 你看了一下所有的程式, 从 permute1.py 到 permute7.py, 再做了一次速度的检定. 反正是最后一次了, 干脆做个大的吧. 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) #!python # calc.py def calc(seq, where): maximum, max_item = 0, [] for i in seq: product = int(i[:where]) * int(i[where:]) if product > maximum: maximum, max_item = product, i elif product == maximum: max_item += ','+i print "Maximum at", max_item, ",product", maximum def calc2(seq, where): maximum, max_item = 0, [] for i in seq: product = int(i[:where]) * int(i[where:]) if product > maximum: maximum, max_item = product, i elif product == maximum: max_item += ','+i rev = list(i) rev.reverse() i = ''.join(rev) product = int(i[:where]) * int(i[where:]) if product > maximum: maximum, max_item = product, i elif product == maximum: max_item += ','+i print "Maximum at", max_item, ",product", maximum $ time python permute2.py 123456789 5 Page 11 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 嗯, 很不错. 最快的要比原先快上近七倍呢! 於是你打算明天一有空便把这个最好的公式贴到 网上去, 让更多人分享. 你很放心地去睡觉了. 但是不知为了什么, 你总觉得有些事烦扰著你, 还有什么不妥的地方呢? 你实在想不到了, 迷 迷糊糊地抱著迷惑不安的心情入梦. 终於你忍不住爬了起床, 再一次回到电脑屏幕前. 你想到了一个致命的问题, 对於很大很大的 排列, permute7.py 还是会尝试一下子把所有的排列都做出来, 不用多久电脑资源就会被耗光 的. 你也许要另想一个方法, 每次只做一个排列. 但你是否可以把所有的排列用 1, 2, 3, 4 的方法数出来呢? 你看著教科书上的那幅图画, 这样的树状结构应该有办法的, 你对自己说. 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 Page 12 of 18一切从游戏开始 - ChinesePython Wiki 2004-5-14http://www.chinesepython.org/cgi_bin/moingb.cgi/_d2_bb_c7_d0_b4_d3_d3_... 慢慢读著书上的文字. 设想有 n 个数字, 先取第一个数字. 再取第二个数字, 第二个数可以放 在第一个数的左或右面, 就是有 0, 1 两个选择. 再取第三个数, 放到前面选好的两个数字中, 可以放在最左, 中间, 最右, 就是有 0, 1, 2 三个选择. 嗯, 很自然吗. 忽然你想到了二进 位, 八进位那些数系转换关系. "我可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 化表放第三个数字的三个位子, 然后百 位数是四进位, 千位数是五进位