::-- ZoomQuiet [2005-03-20 06:05:51]

Contents

一切从游戏开始:

• 故事虚构, 是从一个真的游戏再综合新闻组的内容而来.

缘起

`把五个数字 56789, 放到 [][][] * [][], 令结果最大.`

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

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

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

```%python permute1.py
Maxmum at 87596 ,product 84000```

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

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

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

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

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

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

第二天

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

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

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

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

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

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

```   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 def calc2(seq, where):
13   maximum, max_item = 0, []
14   for i in seq:
15     product = int(i[:where]) * int(i[where:])
16     if product > maximum:
17        maximum, max_item = product, i
18     elif product == maximum:
19        max_item += ','+i
20     rev = list(i)
21     rev.reverse()
22     i = ''.join(rev)
23     product = int(i[:where]) * int(i[where:])
24     if product > maximum:
25        maximum, max_item = product, i
26     elif product == maximum:
27        max_item += ','+i
28   print "Maximum at", max_item, ",product", maximum
```

```\$ 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```

终篇

```把数字 56789 放到
[][][]*[][] 里

```假设五个数为  [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```

```   d e
a  3 2
b  2 1
c  1 0```

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

```   d e
a  4 3
b  3 2
c  2 1```

b 的贡献: b * d * 100 + b * e * 10 e 的贡献: e * a * 100 + e * b * 10 + e * c

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

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

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

检讨总结

1. 把问题规范成一个普遍的形式,这样更容易和别人交流以及找相关资料.
2. 自己尝试找答案.
3. 在网上搜寻更好的答案.
4. 想一个方法来打败这个更好的答案.
5. 翻查教科书或是文献,从基本开始思考有没有最好的解.这些书能被选成教本一定有它的原因.
6. 研究问题的特殊情况, 也许会有别出心裁的巧妙方法.

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

```本文第一次发表在 http://www.dohao.org 技术论坛
2002年许由 glace 整理到中蟒 Wiki 中
2005-3-19 ZoomQuiet 珍藏到 啄木鸟Wiki 中```

反馈

• 怎么看也不厌哪！！隽永的Python小品！ -- ZoomQuiet

AllStartFromGame (last edited 2014-04-21 08:04:54 by ZoomQuiet)

• Page.execute = 1.579s
• Page.execute|1 = 0.414s
• getACL = 0.366s
• init = 0.017s
• load_multi_cfg = 0.000s
• run = 3.353s
• send_page = 3.255s
• send_page_content = 1.660s
• send_page_content|1 = 1.244s
• send_page_content|2 = 0.162s
• send_page|1 = 1.382s
• send_page|2 = 0.218s
• total = 3.369s