一切從游戲開始:
* 故事虛構, 是從一個真的游戲再綜合新聞組的內容而來. 
緣起: 
這是一個晴朗的星期六下午, 你悠閑地在網上瀏覽. 忽然間你看到一個留言板上的小游戲. 它很簡單, 
問題是: 把五個數字?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