缘起

这是一个晴朗的星期六下午, 你悠闲地在网上浏览. 忽然间你看到一个留言板上的小游戏. 它很简单,

问题是: 

把五个数字 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 \
               b!=c and b!=d and b!=e and \
               c!=d and c!=e and d!=e:
  10               result.append(''.join([a,b,c,d,e]))
  11   return result
  12 
  13 seq = list("56789")
  14 where = 3
  15 thelist = permute(seq)
  16 import calc
  17 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

哇! 的确不是盖的. 很好, 而且现在你知道了别人不知的新答案. 就把它贴上去罢. 就在你决定的时候按钮之际, 你到底犹豫了: "我对这个算法不是很了解, 如果别人问起的话怎样回答呢? 这会让我像个东抄西抄的小偷呢! 不, 要不我要明白它的原理, 不然就自己做一个比它更好的." 你觉得壮志无限.

但是现在已经很晚, 你要去睡了. 无奈你在床上反覆地思考著更好的方法, 你整个晚上都没睡好.

待续......