《全排列算法讨论》word版.doc

全排列算法讨论 2你非常自豪.但这也许是适当的时候提醒自己谦虚的妤处.既然都到了这个地步了,何不再走多一步,翻一下书看看,也许你找到的方法已经早有别人发现了.果真是这样的话,你,一个无知的白痴,到处大吹大擂自己的发明是会被笑话的.于是你找出了封尘的电脑和数学教科书.找到了排列组合一章,开始细读.终于你找到了这样的一幅图画：43213421321324121231.3214213.1321.21231.213.书中写到,要产生一个排列其实可以用这样一个方法：先选一个数1,然后第二个数2可以放在1的前面或是后面.而每一个放法都会产生一个2位数,对于每一个这样的两位数,第三个数3,都可以放在它的前面,中间,或是最后；如此产生一个3位数；而每一个3位数,第4位数都可以插入到这3个数的任何一个空位中,如此类推.书中还列出了一个程式范例呢！并声这个方法要和已知的最快的算排列的方法速度相若.你急不可待地开始把书中的描述实现.用Python,你很快又得到了一个全新的程式：1#permute6.py2def permute(seq)：3 seqn=seq.pop()4 while seq：5 newseq=6 new=seq.pop()7#printseq：,seq,seqn,seqn,new,new8 for iin range(len(seqn)：9 item=seqni10 for jin range(len(item)+1)：11 newseq.append(.join(item：j,new,itemj：)12 seqn=newseq13#printnewseq,newseq14 return seqn1516import sys,calc17seq=list(sys.argv1)18where=int(sys.argv2)19thelist=permute(seq)20printGot,len(thelist),items.21calc.calc(thelist,where)测试结果如下：$time cpython permute6.py 1234567 4Got 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上面就是permute7.py产生的四位数字排列结果,你细心地反覆观看,终于看出了一些端倪：其实所产生的排列是有一种对称性的,第一个和最后一个是完全次序相反的,而第二个又和倒数第二个完全相反.利用这些对称性,也许你可以把计算时间打个对折哟.而你研究了一下程式的实现方法后你发现只要改一行！就可以实现这样的功能：就是第一行seqn=seq.pop()改成seqn=seq.pop()+seq.pop().这样你就实现了只产生其中一半的排列,尔后你只要把这个列表中的元素都掉个就完成了整个排列.程式如下1#permute7.py2def permute(seq)：3 seqn=seq.pop()+seq.pop()4 while seq：5 newseq=6 new=seq.pop()7#printseq：,seq,seqn,seqn,new,new8 for iin range(len(seqn)：9 item=seqni10 for jin range(len(item)+1)：11 newseq.append(.join(item：j,new,itemj：)12 seqn=newseq13#printnewseq,newseq14 return seqn1516import sys,calc17seq=list(sys.argv1)18where=int(sys.argv2)19thelist=permute(seq)20printGot,len(thelist),items.21print thelist22#这个等一下再探讨23#calc.calc2(thelist,where)测试数据表示果然这个改良了的程式要比原来快了刚好一倍.这次应该足够了.但是要得到整个排列的话要把这半个列表重抄一次而且每个元素都要反过来：1234-4321.但是在Python之中的字串并没有反序的函数,因此你必须先把字串变成列表,再反过来,然而list.reverse()这个函数偏偏很讨厌的不会传回任何值(因为它是in-place的缘故),所以你要用i=list(item)；i.reverse；i=.join(i)；这个复杂的方法.你想了想,这个做法大概会把原来只做一半排列所省下来的时间都浪费掉了.你思考半天,终于决定重写calc.py部份以便直接利用已知的半个列表.#！python#calc.py def calc(seq,where)：maximum,max_item=0,for iin seq：product=int(i：where)*int(iwhere：)if product maximum：maximum,max_item=product,i elif product=maximum：max_item+=,+i printMaximum at,max_item,product,maximum def calc2(seq,where)：maximum,max_item=0,for iin seq：product=int(i：where)*int(iwhere：)if product maximum：maximum,max_item=product,i elif product=maximum：max_item+=,+i rev=list(i)rev.reverse()i=.join(rev)product=int(i：where)*int(iwhere：)if product maximum：maximum,max_item=product,i elif product=maximum：max_item+=,+i printMaximum at,max_item,product,maximum当然你保留了以前的函数calc而只是新加一个专门给permute7.py调用的calc2函数.你试了一下速度,成功了比permute6.py快了一丁点.虽然只是这一点儿点儿,你也觉得快活无比.因为又一次,你为一个大家都觉得好的方法做出了改良.虽然你知道在这个阶段如果你把calc.py整合到排列产生器中也许会得更好的提速效果,但你觉得现在这样已经可以很多人都认同你的能力了.而且能把一个高效的排列产生器独开来也许是聪明的做法,因为将来你一定会再用它的.你看了一下所有的程式,从permute1.py到permute7.py,再做了一次速度的检定.反正是最后一次了,干脆做个大的吧.$ti me python permute2.py 123456789 5Got 362880 items.Maximum at 875319642,product 843973902 real 0m 46.478s user 0m 46.020s sys 0m0.430s$time python permute3.py 123456789 5Got 362880 items.Maximum at 875319642,product 843973902 real 0m 38.997s user 0m 38.600s sys 0m0.400s$time python permute4.py 123456789 5Got 362880 items.Maximum at 875319642,product 843973902 real 0m 33.845s user 0m 33.460s sys 0m0.380s$time python permute5.py 123456789 5Got 362880 items.Maximum at 875319642,product 843973902 real 0m 10.681s user 0m 10.530s sys 0m0.150s$time python permute6.py 123456789 5Got 362880 items.Maximum at 875319642,product 843973902 real 0m8.279s user 0m8.110s sys 0m0.170s$time cpython permute7.py 123456789 5Got 181440 items.Maximum at 875319642,product 843973902 real 0m7.827s user 0m7.650s sys 0m0.180s嗯,很不错.最快的要比原先快上近七倍呢！于是你打算明天一有空便把这个最好的公式贴到网上去,让更多人分享.你很放心地去睡觉了.但是不知为了什么,你总觉得有些事烦扰著你,还有什么不妥的地方呢?你实在想不到了,迷迷糊糊地抱著迷惑不安的心情入梦.终于你忍不住爬了起床,再一次回到电脑屏幕前.你想到了一个致命的问题,对于很大很大的排列,permute7.py还是会尝试一下子把所有的排列都做出来,不用多久电脑资源就会被耗光的.你也许要另想一个方法,每次只做一个排列.但你是否可以把所有的排列用1,2,3,4的方法数出来呢?你看著教科书上的那幅图画,这样的树状结构应该有办法的,你对自己说.慢慢读著书上的文字.设想有n个数字,先取第一个数字.再取第二个数字,第二个数可以放在第一个数的左或右面,就是有0,1两个选择.再取第三个数,放到前面选好的两个数字中,可以放在最左,中间,最右,就是有0,1,2三个选择.嗯,很自然吗.忽然你想到了二进位,八进位那些数系转换关系.我可以设计这样一个数,.xyz,其中个位数z是二进位的,也就是放第二个数的两个位置；十位数y是三进位的,化表放第三个数字的三个位子,然后百位数是四进位,千位数是五进位的,依以类推.没错,这样设计的话,如果0表示放于最左面的话,则2021这个数就代表了排列五个元素(abcde),取一个a,然后第二个b放在a的右面成ab,取c放到最右面成为abc,取d放到最左面成dabc；最后e放到中间去成为daebc.至于2021这个特别的设计的数可以用.+x*4+y*3+z*2这样的计算来映对到自然数的数列上去.没错了,如求4个数的4！=24个排列,第18个排列可以这样求得,18除2,余数是0,所以第二个数放在第一个数的左面；然后商9再除3,余数0,所以第三个数于在头两个数的最左；最后3除以4,余数是3,因此第四个数要放在前三个数的第4个空位,也就是最右面.利用这个方法,你就不必先求出整个排列才能开始计算.尽管这好像牺牲了时间,但省下了大量的空间.你完全可以算出1000个数的最大排列方法,纵使那可能要用去几个月的运算.你更高兴的是用这个方法,你可以把整个计算拆开成为一个一个的部份：譬如说求10！=3628800个排列,你大可以把1到1000000让一部电脑做,1000001到2000001让另一部来做.大家的工作并不重覆,这等于实现并行运算了！啊哈！妙极了！忽然你灵光一闪,对了,这个不正是permute4.py的算法吗！你昨天还久思不得其解呢,现在你已经完全明白了.呜,虽然这么好的算法原来不是你原创的,但是你仍然异常兴奋.因为你的思路竟和那些大牛们互相吻合.你渐渐记起了当你还在玩DOS游戏机的年代,曾有个古怪的人向你吹嘘过某个电脑扑克游戏中用了一个威力很大的洗牌法,多么的快而且公平,不必怕黑客们用已知的随机数表来出千.现在你猜到了,那个算法很可能就是眼下这一个了.有52张牌,如果要预先算出52！个排列才能洗牌可真要命呢.你觉得舒服多了,你整理了一下程式,打算把结果告诉大家.然而刚才的不安感又重新来袭.你再看了一次最后也应该是最棒的程式,心中安慰自己道：千万不要跌进低等程式员的的陷阱,他们疯也似的不断追求,郤从来不知道自己的目标,也不知道什么才是好.完美的设计不在于你无法添加新的功能,完美的设计是再也不能精简现有的功能.你觉得permute7.py已迫近了这一个极限.但你内心深处并没有因此而舒坦开来,一种悬空的感觉自足下升起.也许是你太累了,于是者你决定闭目养神数分钟再开始上网,可惜你很快地迷迷糊糊地进入了梦境.待续.终篇：你做了一个梦,梦中你看到阿凡提骑著他那出名的毛驴来到你面前并向你提出挑战：除非你解答了我的难题,不然我的驴子会不停在你耳边嘶叫令你无法睡好！问题是：把数字56789放到*里得出最大的的乘积.你发出会心的微笑,正想祭出你的permute7.py之时忽然想起阿凡提是不可能懂得电脑编程的！你心中登时凉了一大截：阿凡提的方法一定不必用电脑算出所有的排列方法,并很快的得知答案的.随著一声震天的驴嘶,你惊醒了,发现原来你伏在电脑桌上睡去了,不小心压著了键盘上的方向键而令你的电脑发出了痛苦的BEEP声.回想梦境,你打算暂时离开电脑,回到问题本身上来：怎样才能看出最大的乘积呢?你拿出纸笔,开始计算：假设五个数为ac*de,展开的话成为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 ea 1000 100 b100 10 c10 1你这样想到：在整个答案中,a带来的页献是一个百位数加上一个十位数,而d的页献是一个百位数加十位数加个位数,因此d要比a更重要.要取得最大的积则一定要把56789中最大的9放在d的位置,然后是a,如此类推.为了方便计算,你干脆用对数来记数100=10e2,用2来代表好了,因此：d ea 32 b2 1c 10计算每一行或列的和,把它称为该数的基值,我们得到a=5,b=3,c=1,d=6,e=3.咦?b和e的基值是一样的,怎么办！你思考著：啊哈！因为我们用了对数,而log(1)=0因此把b和e之间的微小分别给忽略了！好吧,试把每个数都加大一个,得到：d ea 43 b3 2c 21这样基数变成了：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.1def solve(seq,where)：2 n=len(seq)3 seq.sort()4 seq.reverse()5 table=for iin range(n)6 left,right=where,n-where7 leftr=long(1*left)8 rightr=long(1*right)9 flag=10 for item inint(x)for xin seq：11 for iin range(left)：12 tableleft-i-1=(leftr+10*i)*rightr13 for iin range(right)：14 tableright-i+where-1=leftr*(rightr+10*i)15 for iin flag：16 tablei=017 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,rightr26 return leftr,rightr2728import sys29leftr,rightr=solve(list(sys.argv1),int(sys.argv2)30printMaximum at,leftr,rightr,product,leftr*rightr你验算了一下结果,完全正确！这时你好奇地再次time了一下程式的速度$time python permute7.py 123456789 5Got 181440 items.Maximum at 875319642,product 843973902 real 0m7.827s user 0m7.650s sys 0m0.180s$time python wise2.py 123456789 5Maximum at 87531 9642,product 843973902 real 0m0.042s user 0m0.010s sys 0m0.030s哇！快了近两百倍！当然了.如果算更多位的排列会快更多,因为wise.py跳离了n！的限制.你现在觉得舒服多了.你真的解了这个问题.你不再怕有人会写出更快10倍的程式了.你既有了聪明的答案(软解)来对付阿凡提和他的驴子,而在硬解方面,你也自信有世界第一流的排列产生器.你完全满足了,你不再感到疲累,心中疑犹一扫而空.这时你身体感到一阵震栗但心中却喜乐无穷,你第一次感受到了编程之道的洗礼.并且,你学会了所有程式大师都有的态度：我没法用中文来形容,这种态度叫做to hack.你知道只要你熟练并保持这种态度来面对生命中的难题,你很快就可以满师出山了.你最后一次浏览了一下你的程式码,发现在wise.py中,其实每一个循环完成后,最重要的位置和最次要的位子都是不容争议的,因此大可放心地替换两个数字而不是一个,那程式可以再快一倍.不过你觉得现在己经很够了,你颇有禅机地自言自语道：我已经找到明月,再纠缠只下去只是妄执于指月的手而已.你熟练地登出系统并关上电脑,你知道这次你可以真正安心地睡一觉了.哎哟！天已亮了,今天是礼拜一,你要上班的.喔！又要被老板说上班一条虫,下班一条龙.惨.全篇完.课后检讨：一)在上面的故事中,我们看到了解决编程问题的五个方法