1. 從游戲開始:
2. 第二天:
3. 守夜人:
4. 終篇:
5. 課后檢討:

一切從游戲開始:

• 故事虛構, 是從一個真的游戲再綜合新聞組的內容而來.

緣起:

這是一個晴朗的星期六下午, 你悠閑地在網上瀏覽. 忽然間你看到一個留言板上的小游戲. 它很簡單,

問題是: 把五個數字 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 

沒問題. 現在你只要給出所有的排列即可. 你打了幾行, 覺得 [5,6,8,7,9] 這樣打太辛苦了, 而且用 i[0]*100 + i[1]*10 ... 的方法好像太難看了, 因此你有必要做一次修改. 好, 用字串吧. "56789", 這樣輸入時較方便, 而且 int("567") * int("89") 要好看得多, 也應該快些. 另外你也把程式改得更短, 看起來像是個有經驗的人所寫.

    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)

嗯, 好些了. 那句 if __name__ == "__main__" 是為了將來你把 calc.py 做為模組來用時而設的. 在別的程式中用 import calc 的話那幾行就不會運行了.

現在你可以隨自己的意來解更普遍的問題, 比如 123 放在 []*[][], 或是 1234567 放在 [][][][]*[][][] 這樣的問法. 現在你開始輸入排列了. "56789", "56798", "56879", "56897", .......... 沒多久你又覺得自己太愚蠢了, 為什么不叫電腦程式自動產生這些無聊的排列呢? 56789 一共有 5! 也就是 120 種排列方法呢! 如果你想算 123456789 的話, 用手輸入可能要用去一生的時間!!

於是你開始想如何產生排列的算法了. 用循環就可以了, 不過循環會產生重覆的組合, 譬如 555*55. 但我們可以加些條件式進去把重覆項拿走. 於是你有了第一個程式解.

    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)

你小心地記著用 ''.join() 的方法產生字串要比用 a+b+c+d 快, 同時也認為用 import calc 的方式會讓你更容易為不同的地方做些速度的微調. 你開始運行程式了:

%python permute1.py 
Maxmum at 87596 ,product 84000 

你成功了. 啊哈, 你認為可以貼到留言板上去領賞了. 經過一些考慮后, 你覺得還是要做到更普遍的功能, 就是讓用戶輸入排列多少個數字, 怎樣分割. 研究了一下程式, 你覺得用循環好像無法達到要求, 因為你事前并不知道要排多少個數字, 因此你不知道要寫多少個循環才夠. 面對這種情況, 你好像只能用遞歸的方法了.

你知道如何求得, 例如, 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 個數字的排列問題, 直到要求的排列只剩下一個數.

以下就是你的函數, 不過你還不知道它到底是不是正確的, 因為寫遞歸函數很易出錯, 因此你要先試一下.

    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'] 

看來是正確的. 但有沒有辦法再快一些呢? 你想了半天, 終於發現其實你不必等到 l = 1 的時候才有所動作, 你可以在 l = 2 的時候就干些事了. 因為你知道 l = 2 的話, 排列一定是 [ [0,1], [1,0] ] 的, 這樣你起碼可以用些力氣幫電腦一把. 當然如果你把 l = 3 的排列也寫出來更好, 但寫到 l = 4 或以上大可不必了. 這種幫它一下的做法在程式優化中的學名是 unroll, 你隱約記得是學過的. 好, 現在你有另一個程式了.

    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

現在你可以正式測試了. 你把 permute3.py 改了一下, 以便可以從命令行取得數字以及分割方法. 程式變成下面的樣子, 同時你也對 permute2.py 做了相同的修改.

    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 方式來看程式到底運行了多長時間吧.

$ time python permute2.py 56789 3 
Got 120 items. 
Maximum at 87596 ,product 84000 
 
real    0m0.057s 
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 

呵, 不錯. 修改了的就是快些. 到了這個地步, 你開始覺得好奇了. 像求排列這樣一個常見的問題, 不知道別人都是怎樣做的呢. 也許應該到網上去找找看, 或者有一兩個已經寫好的程式片斷可以抄的. 你可不想弄錯一個原來己經有標準答案的問題. 把 permute2.py 貼上留言板或者會令自己看起來像一個三流的程式設計員, 這可是你最不想見到的. 於是你在網上到處搜尋. 不過似乎都是以遞歸算法為主的, 直至用了一些時間, 你終於在 ASPN: 的網上程式碼收集站上看到了這一個片斷:

    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)

作者聲稱這個算法的量級是 O(n) 的. 你覺得難以置信, 但不妨一試. 由於你理解到這個函數每次只傳回排列中的某一項, 因此你寫了個小程式去驗算它.

    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 

測試顯示這個函數沒問題. 但它怎樣做到的呢? 你研究了一下, 每個不同的 index 值都傳回唯一的排列, 而且大過 n! 的 index 會從頭來算起, divider 每次都要增加一, 列表的排法又是按商余數來重整. 唉, 不得要領. 嗨! 管它呢. 反正能用就行了. 於是你修改 permute4.py, 加入一個新的函數求 factorial, 這樣就可以調用 permute 得到所有的排列. 并進行計時. 你用了更多的數字, 以便速度的差別更明顯些.

    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 

哇! 的確不是蓋的. 很好, 而且現在你知道了別人不知的新答案. 就把它貼上去罷. 就在你決定的時候按鈕之際, 你到底猶豫了: "我對這個算法不是很了解, 如果別人問起的話怎樣回答呢? 這會讓我像個東抄西抄的小偷呢! 不, 要不我要明白它的原理, 不然就自己做一個比它更好的." 你覺得壯志無限.

但是現在已經很晚, 你要去睡了. 無奈你在床上反覆地思考著更好的方法, 你整個晚上都沒睡好.

待續......

第二天:

你醒來第一件事, 洗臉刷牙. 編程愛好者并不一定和終日蓬頭垢面同義. 然后呢, 看看電視報紙, 做些公益活動, 今天是禮拜天嘛. 廢話少說, 終於你在電腦前坐下, 登入了你喜愛的 Slackware / RedHat / Redflag / Mandrake / Debian / WindowsXP / Chinese2000 / DOS / Solaris/ AIX / Unicos / OSX [作者按: 請依實際情況增刪, 但千萬拜托不要把 SCO 也加進來], 這些都是 Python 能夠運行的平臺.

你記起你以前學到遞歸時聽過的話: 任何遞歸/回溯函數都可以還原成非遞歸形式的. 於是你決定用你自己的方式一試. 你默念著求排列的方法, 5 個數取一個, 剩下 4 個, 再取一個, 剩下 3 個 .... 於是你寫出一個新的程式, 和最初的一個很相像:

    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"))

這個程式依次創建 5, 4, 3, 2, 1 個數的列表, 每個都不包括之前被選的數字, 然后把 5 個數合起來完成一種排列.當然, 你還有空間做 unroll. 但現在問題在於, 你對程式的要求是事先并不知道要求多少個數字的排列, 就是你不知道要寫幾個 for 才夠. 但現在你認為有一個好辦法: 既然 Python 是動態的, 它可以執行自己寫出來的編碼, 為什么不叫它自己幫自己來寫這個循環程式以完成工作呢? 你覺得這種讓程式來為自己寫程式的想法很科幻也很妙, 而且讓你記起了以前聽到很多資深程式員愛用的 m4 宏語言. 於是你趕緊試了一個. 你認為可以用 counter0, counter1, counter2...來代替 i, j, l, m...的循環子命名法.

    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
   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. 

看來格式是弄對了. 現在算算運行時間, 會不會好些呢? 也許會比以前更快, 也許因為要再執行自己產生的程式而更慢, 一切都要看實際的數據才能呢! 你修改了 permute5.py 以便它能標準化地計算時間. 你開始覺得 import calc 實在是挺聰明的設計.

    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]))

開始計時:

$ time cpython permute5.py 1234567 4 
Got 5040 items. 
Maximum at 6531742 ,product 4846002 
 
real    0m0.213s 
user    0m0.200s 
sys     0m0.010s 

啊哈! 那個什么量級 O(n) 的也被你打敗!! 你覺得它的量級其實不是 O(n), 那只是對找一整個排列其中一個的時候才有用, 要把整個排列都算出來的話還是要回到 n! 上的.

你非常自豪. 但這也許是適當的時候提醒自己謙虛的妤處. 既然都到了這個地步了, 何不再走多一步, 翻一下書看看, 也許你找到的方法已經早有別人發現了. 果真是這樣的話, 你, 一個無知的白癡, 到處大吹大擂自己的發明是會被笑話的.

於是你找出了封塵的電腦和數學教科書. 找到了排列組合一章, 開始細讀. 終於你找到了這樣的一幅圖畫:

                      [4321]   
                      [3421] 
             [321]  < [3241]      
      [21] < [231]... [3214] 
             [213]... 
[1] < 
             [321]... 
      [21] < [231]... 
             [213]...       

書中寫到, 要產生一個排列其實可以用這樣一個方法: "先選一個數 1, 然后第二個數 2 可以放在 1 的前面或是后面. 而每一個放法都會產生一個 2 位數, 對於每一個這樣的兩位數, 第三個數 3, 都可以放在它的前面, 中間, 或是最后; 如此產生一個 3 位數; 而每一個 3 位數, 第 4 位數都可以插入到這 3 個數的任何一個空位中, 如此類推. 書中還列出了一個程式范例呢! 并聲這個方法要和已知的最快的算排列的方法速度相若.

你急不可待地開始把書中的描述實現. 用 Python, 你很快又得到了一個全新的程式:

    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
   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'] 

上面就是 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 部份以便直接利用已知的半個列表.

#!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 

當然你保留了以前的函數 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 已迫近了這一個 極限. 但你內心深處并沒有因此而舒坦開來, 一種懸空的感覺自足下升起. 也許是你太累了, 于是 者你決定閉目養神數分鐘再開始上網, 可惜你很快地迷迷糊糊地進入了夢境.

待續...

終篇:

你做了一個夢, 夢中你看到阿凡提騎著他那出名的毛驢來到你面前并向你提出挑戰: "除非你解答了我的難題,不然我的驢子會不停在你耳邊嘶叫令你無法睡好! 問題是: 把數字 56789 放到 [][][]*[][] 里得出最大的的乘積...." 你發出會心的微笑, 正想祭出你的 permute7.py 之時忽然想起阿凡提是不可能懂得電腦編程的! 你心中登時涼了一大截: 阿凡提的方法一定不必用電腦算出所有的排列方法, 并很快的得知答案的. 隨著一聲震天的驢嘶, 你驚醒了, 發現原來你伏在電腦桌上睡去了, 不小心壓著了鍵盤上的方向鍵而令你的電腦發出了痛苦的 BEEP 聲.

回想夢境, 你打算暫時離開電腦, 回到問題本身上來: 怎樣才能"看"出最大的乘積呢 ?

你拿出紙筆, 開始計算:

假設五個數為  [a][b][c]*[d][e], 展開的話成為 
 
  a * 100 * d * 10 
+ a * 100 * e * 1 
+ b * 10  * d * 10 
+ b * 10  * e * 1 
+ c * 1   * d * 10  
+ c * 1   * e * 1 
 
這個可以寫成一個矩陣: 
 
      d    e 
a  1000  100 
b   100   10 
c    10    1 

你這樣想到: 在整個答案中, a 帶來的頁獻是一個百位數加上一個十位數, 而 d 的頁獻是一個百位數加十位數加個位數, 因此 d 要比 a 更重要. 要取得最大的積則一定要把 56789 中最大的 9 放在 d 的位置, 然后是 a, 如此類推.

為了方便計算,你干脆用對數來記數 100 = 10e2, 用 2 來代表好了, 因此:

   d e  
a  3 2 
b  2 1 
c  1 0 

計算每一行或列的和, 把它稱為該數的基值, 我們得到

a = 5, b = 3, c = 1, d = 6, e = 3.

咦? b 和 e 的基值是一樣的, 怎么辦!

你思考著: "啊哈! 因為我們用了對數, 而 log(1) = 0 因此把 b 和 e 之間的微小分別給忽略了!" 好吧, 試把每個數都加大一個, 得到:

   d e 
a  4 3 
b  3 2 
c  2 1 

這樣基數變成了: a = 7, b = 5, c = 3, d = 9, e = 6. 這些基數代表了該位置的重要性, 可以按大小分予不同的數字.

好, 按基數的大小來分配數字你得到了 865 * 97. 一對答案, 喲! 不一樣! 正確解是 875 * 96. 哪里不對了呢? 仔細分析下來, 你發現 b 和 e 互換了. 換的原因是這樣的:

b 的頁獻: b * d * 100 + b * e * 10 e 的頁獻: e * a * 100 + e * b * 10 + e * c

粗看的話 e 的頁獻要大一些, 但因為我們把 9 配給了 d 而 8 配給了 a, 因此最終的結果是 b 的實際頁獻要比 e 大. 由於 e 和 b 的基數只相差在 e * c 這個個位數乘積上, d 和 a 之間的分配結果把這個小的差異覆蓋掉了.

你考慮著: "要把這樣的覆蓋也算上去的話, 也許可以做一個二階基數. 如 b * d 的基數是 100, 但是由於 d 的基數為 9, 那 b 的二階基數可以算成 9, 代表和 b 相關的是一個較為重要的數; 同樣 e * a 的基數是也是 100 但由於 a 的基數只是 7, 因此 e 的二階基數只是 7 而已. 這樣就可以得出 b 要比 e 更重要了."

於是你有了一個想法: 先寫出相關矩陣, 然后計算每個數的基數和二階基數, 再進行排序, 當兩個基數很接近時就用二階基數來判別哪個較重要. 嗯, 你覺得自己聰明極了, 於是開始驗算, 但很快又發現其實 b 和 e 的二階基數原來也是一樣的!! 大家都是 15. 也許我們要用一個三階基數才能分辨他們.

你又想了一些新的二階基數的定義, 有些的確給出正確的答案, 但你漸漸覺得這一切并不很妥當. 因為就算能計出 56789, 但是在更多的排列, 如 7 位數甚至 9 位數的排列你怎樣保證答案也一定準確呢, 而兩個基數到底怎樣才算是比較接近呢? 仔細審視你的方法, 用對數來表示乃至直接相加來求所謂的基數統統都是即興的, 毫不嚴謹. 或者要真正解決他們必需要把每一種情況都算進來, 而那樣做的話必然要計算 n! 那么多次! 說到底還是要算排列的.

你有些失望, 但暗中覺得松了一口氣, 因為到底是 permute7.py 得到最后的勝利. 你伸了一下懶腰, 原來天都快亮了. 這時你感到有些餓, 便去拿了半個涼饅頭, 沖了一些可可. 你對著空空的螢光屏, 靜靜地坐了大概十分鐘, 然后答案進入你的腦海, 謎團被解開了.

你的方法是求出所有位置的"重要性"(用你的語言就是求基數), 然后依次把最大的數字分配給最重要的位置. 但是位置的重要性是和其他位置糾纏在一起的, 因此一次過算出所有位置的重要性必須考慮大量不同的組合排列, 并不實際.

但是, 我們其實可以每次只求第一個最大的基數的位置 (abc*de 的情況下最大的基數是 d), 這個最大的基數是沒有爭議的. 當求得這個位置時, 干脆把最大的數字放到該位子上, 然后再求一次基數, 找出接下來最大的位子, 這個位子也是無可爭議的. 如此一來, 原來求 5 個數字的全排列成就簡化為 5 次簡單的回圈. 一個求 Factorial(n) 的問題變成了 n 次循環!

啊哈!

你精神大好, 從另一個角度切入:

假如 5 個數字一樣, 11111, 最大的乘積只能是 111 * 11, 現在容許改大一個數, 改哪個會使結果最大 ?

211 * 11, 121 * 11, 112 * 11, 111 * 21, 111 * 12 ? 答案是 111 * 21, 也就是 d 的位置. 好, 把 d 替換成 9.

問題變成 5 個數字, 111 * 91, 改一個數(除了 9), 改哪一個 ?

211 * 91, 121 * 91, 112 * 91, 111 * 19 ? 答案是 211 * 91, 也就是 a 的位置. 好, 替換成 8.

依此類推, 答案正正是 875 * 96.

你重開電腦, 很快地把新方法輸入程式, 并改名為 wise.py.

    1 def solve(seq,where):
    2   n = len(seq)
    3   seq.sort()
    4   seq.reverse()
    5   table = [ [] for i in range(n) ]
    6   left, right = where, n - where
    7   leftr = long('1'*left)
    8   rightr = long('1'*right)
    9   flag=[]
   10   for item in [ int(x) for x in seq]:
   11     for i in range(left):
   12       table[left-i-1] = (leftr + 10**i) * rightr
   13     for i in range(right):
   14       table[right-i+where-1] = leftr * (rightr + 10**i)
   15     for i in flag:
   16       table[i] = 0
   17     tablesorted = table[:]
   18     tablesorted.sort()
   19     maxindex = table.index(tablesorted[-1])
   20     if maxindex >= where:
   21        rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
   22     else:
   23        leftr = leftr + (item-1) * 10**(left-maxindex-1)
   24     flag.append(maxindex)
   25     #print maxindex, leftr, rightr
   26   return leftr, rightr
   27 
   28 import sys
   29 leftr, rightr = solve(list(sys.argv[1]),int(sys.argv[2]))
   30 print "Maximum at", leftr,rightr, ',product', leftr*rightr

你驗算了一下結果, 完全正確! 這時你好奇地再次 time 了一下程式的速度

$time python permute7.py 123456789 5 
Got 181440 items. 
Maximum at 875319642 ,product 843973902 
 
real    0m7.827s 
user    0m7.650s 
sys     0m0.180s 
 
$ time python wise2.py 123456789 5 
Maximum at 87531 9642 ,product 843973902 
 
real    0m0.042s 
user    0m0.010s 
sys     0m0.030s 

哇! 快了近兩百倍! 當然了. 如果算更多位的排列會快更多, 因為 wise.py 跳離了 n! 的限制.

你現在覺得舒服多了. 你真的解了這個問題. 你不再怕有人會寫出更快 10 倍的程式了. 你既有了"聰明"的答案 (軟解) 來對付阿凡提和他的驢子, 而在硬解方面, 你也自信有世界第一流的排列產生器. 你完全滿足了, 你不再感到疲累, 心中疑猶一掃而空. 這時你身體感到一陣震栗但心中卻喜樂無窮, 你第一次感受到了編程之道的洗禮. 并且, 你學會了所有程式大師都有的態度: 我沒法用中文來形容, 這種態度叫做 "to hack". 你知道只要你熟練并保持這種態度來面對生命中的難題, 你很快就可以滿師出山了.

你最后一次瀏覽了一下你的程式碼, 發現在 wise.py 中, 其實每一個循環完成后, 最重要的位置和最次要的位子都是不容爭議的, 因此大可放心地替換兩個數字而不是一個, 那程式可以再快一倍. 不過你覺得現在己經很夠了, 你頗有禪機地自言自語道: "我已經找到明月,再糾纏只下去只是妄執於指月的手而已." 你熟練地登出系統并關上電腦, 你知道這次你可以真正安心地睡一覺了.

哎喲! 天已亮了, 今天是禮拜一, 你要上班的. 喔! 又要被老板說上班一條蟲, 下班一條龍...... 慘.......

全篇完.

課后檢討:

一) 在上面的故事中,我們看到了解決編程問題的五個方法.

1. 把問題規范成一個普遍的形式,這樣更容易和別人交流以及找相關資料.
2. 自己嘗試找答案.
3. 在網上搜尋更好的答案.
4. 想一個方法來打敗這個更好的答案.
5. 翻查教科書或是文獻,從基本開始思考有沒有最好的解.這些書能被選成教本一定有它的原因.
6. 研究問題的特殊情況, 也許會有別出心裁的巧妙方法.

二) 故事中每個程式都只有二三十行大小,說明 Python 語言表達力強且語意很濃縮, 做為快速開發或是測算自己的想法都是非常好的.

三) Python 程式濃縮之余,它的語言也異常的清晰.回看上面的程式,你會發現它們全都不難明白.這說明 Python 程式更加容易維護.

四) 在故事中,我們有很大的篇幅是在討論方法而只有小部份是在描述 Python 的語言特性.這證明 Python 更適合用來教授編程的概念. 事實上, Python 的作者 Guido 和很多人都認為 Python 是電腦教育的首選語言. 教師可以讓學生靜靜地思考,學通運算的法則; 而不是上來就瘋狂地敲打鍵盤,并要記住一大堆電腦語言的古怪特徵.

五) 整個故事圍繞於算法的改進而較少碰到 Python 程式的優化問題. 也許在續集中(如果有的話), 我們要嘗試一下在固定的算法及盡量少改動程式碼的條件下, 提高 Python 程式的效率. 我暫時想到的方法包括:

1. 利用較新和較快的語法. 如 yield, generator.
2. 用 Python 的自帶優化選項以及內建模組.
3. 用第三方的擴展模組, 如 Numpy, Scipy.
4. 用編譯方式代替解釋, 如 freeze, py2exe.
5. 用 JIT 類的方法, 如 Psyco.
6. 用 Thread, 在多 CPU 的機器上平行運算.
7. 最后一樣要大改程式了, 用 C 來做擴展.
8. 更有 'to hack' 感覺的, 修改 Python 主干程式, 加入像 string.reverse() 這樣的輔助函數.

六) 文中所用的測試硬件:

CPU: Pentium III 866 RAM: 128 MB

文中所用的測試軟件:

Slackware Linux: 9.0 Linux Kernel: 2.4.2 GCC: 3.2.2 Python: 修改過的 2.1.3

七) 啃涼饅頭對腦筋有幫助.

八) 如果你能想到更好的方法, 歡迎聯絡本人: glace_at_chinesepython.org