於是你决定用你自己方式试.你默念著求排列思路方法,5个数取个,剩下4个,再取个,剩下3个....於是你写出个新程式,和最初个很相像:
1#permute5.py
2defpermute(seq):
3result=
4foriinseq:
5seq1=seq[:]
6seq1.remove(i)
7forjinseq1:
8seq2=seq1[:]
9seq2.remove(j)
10forlinseq2:
11seq3=seq2[:]
12seq3.remove(l)
13forminseq3:
14seq4=seq3[:]
15seq4.remove(m)
16result.append(’’.join([i,j,l,m,seq4[0]]))
17result
18
19prpermute(list(\"12345\"))
这个程式依次创建5,4,3,2,1个数列表,每个都不包括的前被选数字,然后把5个数合起来完成种排列.当然,你还有空间做unroll.但现在问题在於,你对程式要求是事先并不知道要求多少个数字排列,就是你不知道要写几个for才够.但现在你认为有个好办法:既然Python是动态,它可以执行自己写出来编码,为什么不叫它自己帮自己来写这个循环程式以完成工作呢?你觉得这种让程式来为自己写程式想法很科幻也很妙,而且让你记起了以前听到很多资深程式员爱用m4宏语言.於是你赶紧试了个.你认为可以用counter0,counter1,counter2...来代替i,j,l,m...循环子命名法.
1#permute5.py
2defgenfunc(n):
3head=\"\"\"
4defpermute(seq0):
5result=\"\"\" [Page]
6boiler=\"\"\"
7forcounter%iinseq%i:
8seq%i=seq%i[:]
9seq%i.remove(counter%i)\"\"\"
10foriinrange(1,n):
11space=’’*i
12head=head+boiler.replace(’\\n’,’\\n’+space)%(i,i-1,i,i-1,i,i)
13temp=’,’.join([’counter%i’%(x)forxinrange(1,n)]+[\"seq%i[0]\"%(n-1)])
14head=head+’\\n’+space+\"result.append(’’.join([%s]))\"%(temp)
15head+’\\nresult\\n’
16
17importsys
18functext=genfunc(len(sys.argv[1]))
19prfunctext
20exec(functext)
21prdir
22thelist=permute(list(sys.argv[1]))
23pr’Got’,len(thelist),’items.’
运行下,
sh-2.05b$pythonpermute5.py123453

defpermute(seq0):
result=
forcounter1inseq0:
seq1=seq0[:]
seq1.remove(counter1)
forcounter2inseq1:
seq2=seq1[:]
seq2.remove(counter2)
forcounter3inseq2:
seq3=seq2[:]


seq3.remove(counter3)
forcounter4inseq3:
seq4=seq3[:]
seq4.remove(counter4)
result.append(’’.join([counter1,counter2,counter3,counter4,seq4[0]])) [Page]
result

[’__builtins__’,’__doc__’,’__name__’,’calc’,’functext’,’genfunc’,
’permute’,’sys’]
Got120items.

看来格式是弄对了.现在算算运行时间,会不会好些呢?也许会比以前更快,也许要再执行自己产生程式而更慢,切都要看实际数据才能呢!你修改了permute5.py以便它能标准化地计算时间.你开始觉得importcalc实在是挺聪明设计.
1#permute5.py
2defgenfunc(n):
3head=\"\"\"
4defpermute(seq0):
5result=\"\"\"
6boiler=\"\"\"
7forcounter%iinseq%i:
8seq%i=seq%i[:]
9seq%i.remove(counter%i)\"\"\"
10foriinrange(1,n):
11space=’’*i
12head=head+boiler.replace(’\\n’,’\\n’+space)%(i,i-1,i,i-1,i,i)
13temp=’,’.join([’counter%i’%(x)forxinrange(1,n)]+[\"seq%i[0]\"%(n-1)])
14head=head+’\\n’+space+\"result.append(’’.join([%s]))\"%(temp)
15head+’\\nresult\\n’
16
17importsys,calc
18functext=genfunc(len(sys.argv[1]))
19#prfunctext
20exec(functext)
21thelist=permute(list(sys.argv[1]))
22pr’Got’,len(thelist),’items.’
23calc.calc(thelist,(sys.argv[2]))
开始计时:
$timecpythonpermute5.py12345674
Got5040items.
Maximumat6531742,product4846002

real0m0.213s
user0m0.200s [Page]
sys0m0.010s

啊哈!那个什么量级O(n)也被你打败!!你觉得它量级其实不是O(n),那只是对找整个排列其中个时候才有用,要把整个排列都算出来话还是要回到n!上.
你非常自豪.但这也许是适当时候提醒自己谦虚妤处.既然都到了这个地步了,何不再走多步,翻下书看看,也许你找到思路方法已经早有别人发现了.果真是这样话,你,个无知白痴,到处大吹大擂自己发明是会被笑话.
於是你找出了封尘电脑和数学教科书.找到了排列组合章,开始细读.终於你找到了这样幅图画:
[4321]
[3421]
[321]<[3241]
[21]<[231]...[3214]
[213]...
[1]<
[321]...
[21]<[231]...
[213]...

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


你急不可待地开始把书中描述实现.用Python,你很快又得到了个全新程式:1#permute6.py
2defpermute(seq):
3seqn=[seq.pop]
4whileseq:
5seq= [Page]
6=seq.pop
7#pr\"seq:\",seq,’seqn’,seqn,’’,
8foriinrange(len(seqn)):
9item=seqn[i]
10forjinrange(len(item)+1):
11seq.append(’’.join([item[:j],,item[j:]]))
12seqn=seq
13#pr’seq’,seq
14seqn
15
16importsys,calc
17seq=list(sys.argv[1])
18where=(sys.argv[2])
19thelist=permute(seq)
20pr’Got’,len(thelist),’items.’
21calc.calc(thelist,where)
测试结果如下:
$timecpythonpermute6.py12345674
Got5040items.
Maximumat6531742,product4846002

real0m0.167s
user0m0.150s
sys0m0.020s

哇塞!书中自有黄金屋咧!想不到这个才是最快算法.