终篇
你做了一个梦, 梦中你看到阿凡提骑著他那出名的毛驴来到你面前并向你提出挑战: "除非你解答了我的难题,不然我的驴子会不停在你耳边嘶叫令你无法睡好! 问题是:
把数字 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 中, 其实每一个循环完成后, 最重要的位置和最次要的位子都是不容争议的, 因此大可放心地替换两个数字而不是一个, 那程式可以再快一倍. 不过你觉得现在己经很够了, 你颇有禅机地自言自语道: "我已经找到明月,再纠缠只下去只是妄执於指月的手而已." 你熟练地登出系统并关上电脑, 你知道这次你可以真正安心地睡一觉了.
哎哟! 天已亮了, 今天是礼拜一, 你要上班的. 喔! 又要被老板说上班一条虫, 下班一条龙...... 惨.......
全篇完.