回溯与递归:任何递归/回溯函数都可以还原成非递归形式来源: 发布时间:星期四, 2009年2月12日 浏览:44次 评论:0
於是你决定用你自己方式试.你默念著求排列思路方法,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 哇塞!书中自有黄金屋咧!想不到这个才是最快算法. 0
相关文章读者评论发表评论 |