'''第二天'''

你醒来第一件事, 洗脸刷牙. 编程爱好者并不一定和终日蓬头垢面同义. 然后呢, 看看电视报纸, 做些公益活动, 今天是礼拜天嘛. 废话少说, 终於你在电脑前坐下, 登入了你喜爱的 Slackware / RedHat / Redflag / Mandrake / Debian / WindowsXP / Chinese2000 / DOS / Solaris/  AIX / Unicos / OSX [作者按: 请依实际情况增删, 但千万拜托不要把 SCO 也加进来], 这些都是 Python 能够运行的平台.

你记起你以前学到递归时听过的话: 任何递归/回溯函数都可以还原成非递归形式的. 於是你决定用你自己的方式一试. 你默念著求排列的方法, 5 个数取一个, 剩下 4 个, 再取一个, 剩下 3 个 .... 於是你写出一个新的程式, 和最初的一个很相像:

{{{
#!python
# permute5.py
def permute(seq):
  result = []
  for i in seq:
    seq1 = seq[:] 
    seq1.remove(i)
    for j in seq1:
      seq2 = seq1[:]
      seq2.remove(j)
      for l in seq2:
        seq3 = seq2[:]
        seq3.remove(l) 
        for m in seq3:
          seq4 = seq3[:]
          seq4.remove(m)
          result.append(''.join([i,j,l,m,seq4[0]]))
  return result

print permute(list("12345"))
}}}

这个程式依次创建 5, 4, 3, 2, 1 个数的列表, 每个都不包括之前被选的数字, 然后把 5 个数合起来完成一种排列.当然, 你还有空间做 unroll. 但现在问题在於, 你对程式的要求是事先并不知道要求多少个数字的排列, 就是你不知道要写几个 for 才够. 但现在你认为有一个好办法: 既然 Python 是动态的, 它可以执行自己写出来的编码, 为什么不叫它自己帮自己来写这个循环程式以完成工作呢? 你觉得这种让程式来为自己写程式的想法很科幻也很妙, 而且让你记起了以前听到很多资深程式员爱用的 m4 宏语言. 於是你赶紧试了一个. 你认为可以用 counter0, counter1, counter2...来代替 i, j, l, m...的循环子命名法. 

{{{
#!python
# permute5.py
def genfunc(n):
  head = """
def permute(seq0):
  result = [] """
  boiler = """
for counter%i in seq%i:
  seq%i = seq%i[:]
  seq%i.remove(counter%i)""" 
  for i in range(1,n):
    space = '  '*i
    head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
  temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
  head = head + '\n' + space + "  result.append(''.join([%s]))"%(temp)
  return head + '\n  return result\n' 
    
import sys
functext = genfunc(len(sys.argv[1]))
print functext
exec(functext)
print dir()
thelist = permute(list(sys.argv[1]))
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.
}}}

看来格式是弄对了. 现在算算运行时间, 会不会好些呢? 也许会比以前更快, 也许因为要再执行自己产生的程式而更慢, 一切都要看实际的数据才能呢! 你修改了 permute5.py 以便它能标准化地计算时间. 你开始觉得 import calc 实在是挺聪明的设计.

{{{
#!python
# permute5.py
def genfunc(n):
  head = """
def permute(seq0):
  result = [] """
  boiler = """
for counter%i in seq%i:
  seq%i = seq%i[:]
  seq%i.remove(counter%i)"""
  for i in range(1,n):
    space = '  '*i
    head = head + boiler.replace('\n','\n'+space)%(i,i-1,i,i-1,i,i)
  temp = ','.join([ 'counter%i'%(x) for x in range(1,n) ] + ["seq%i[0]"%(n-1)])
  head = head + '\n' + space + "  result.append(''.join([%s]))"%(temp)
  return head + '\n  return result\n'

import sys, calc
functext = genfunc(len(sys.argv[1]))
#print functext
exec(functext)
thelist = permute(list(sys.argv[1]))
print 'Got',len(thelist),'items.'
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
}}}

啊哈! 那个什么量级 O(n) 的也被你打败!! 你觉得它的量级其实不是 O(n), 那只是对找一整个排列其中一个的时候才有用, 要把整个排列都算出来的话还是要回到 n! 上的. 

你非常自豪. 但这也许是适当的时候提醒自己谦虚的妤处. 既然都到了这个地步了, 何不再走多一步, 翻一下书看看, 也许你找到的方法已经早有别人发现了.  果真是这样的话, 你, 一个无知的白痴, 到处大吹大擂自己的发明是会被笑话的. 

於是你找出了封尘的电脑和数学教科书. 找到了排列组合一章, 开始细读. 终於你找到了这样的一幅图画:

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

书中写到, 要产生一个排列其实可以用这样一个方法: "先选一个数 1, 然后第二个数 2 可以放在 1 的前面或是后面. 而每一个放法都会产生一个 2 位数, 对於每一个这样的两位数, 第三个数 3, 都可以放在它的前面, 中间, 或是最后; 如此产生一个 3 位数; 而每一个 3 位数, 第 4 位数都可以插入到这 3 个数的任何一个空位中, 如此类推. 书中还列出了一个程式范例呢! 并声这个方法要和已知的最快的算排列的方法速度相若. 

你急不可待地开始把书中的描述实现. 用 Python, 你很快又得到了一个全新的程式:

{{{
#!python
# permute6.py
def permute(seq):
  seqn = [seq.pop()]
  while seq:
    newseq = []
    new = seq.pop()
    #print "seq:",seq,'seqn', seqn ,'new', new
    for i in range(len(seqn)):
      item = seqn[i]
      for j in range(len(item)+1):
        newseq.append(''.join([item[:j],new,item[j:]]))
    seqn = newseq
    #print 'newseq',newseq
  return  seqn

import sys, calc
seq = list(sys.argv[1])
where = int(sys.argv[2])
thelist = permute(seq)
print 'Got', len(thelist), 'items.'
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
}}}

哇塞! 书中自有黄金屋咧! 想不到这个才是最快的算法. 你开始感到要击败这次的对手不是不件容易的事, 而且现在已经很晚了, 你身心也都被疲倦所包围著. 你绝望地看著这个新的程式码和它那美妙的结构, 作出最后的尝试:


待续...