'''终篇 '''

你做了一个梦, 梦中你看到阿凡提骑著他那出名的毛驴来到你面前并向你提出挑战: "除非你解答了我的难题,不然我的驴子会不停在你耳边嘶叫令你无法睡好! 问题是: 
{{{
把数字 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. 

{{{
#!python
def solve(seq,where):
  n = len(seq)
  seq.sort()
  seq.reverse()
  table = [ [] for i in range(n) ]
  left, right = where, n - where
  leftr = long('1'*left)
  rightr = long('1'*right)
  flag=[]
  for item in [ int(x) for x in seq]:
    for i in range(left):
      table[left-i-1] = (leftr + 10**i) * rightr
    for i in range(right):
      table[right-i+where-1] = leftr * (rightr + 10**i)
    for i in flag:
      table[i] = 0
    tablesorted = table[:]
    tablesorted.sort()
    maxindex = table.index(tablesorted[-1])
    if maxindex >= where:
       rightr = rightr + (item-1) * 10**(right-maxindex+where-1)
    else:
       leftr = leftr + (item-1) * 10**(left-maxindex-1)
    flag.append(maxindex)
    #print maxindex, leftr, rightr
  return leftr, rightr

import sys
leftr, rightr = solve(list(sys.argv[1]),int(sys.argv[2]))
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 中, 其实每一个循环完成后, 最重要的位置和最次要的位子都是不容争议的, 因此大可放心地替换两个数字而不是一个, 那程式可以再快一倍. 不过你觉得现在己经很够了, 你颇有禅机地自言自语道: "我已经找到明月,再纠缠只下去只是妄执於指月的手而已." 你熟练地登出系统并关上电脑, 你知道这次你可以真正安心地睡一觉了.

哎哟! 天已亮了, 今天是礼拜一, 你要上班的. 喔! 又要被老板说上班一条虫, 下班一条龙...... 惨.......

全篇完.