故事虛構(gòu),是從一個真的游戲再綜合新聞組的內(nèi)容而來.

緣起

緣起

這是一個晴朗的星期六下午,你悠閑地在網(wǎng)上瀏覽.忽然間你看到一個留言板上的小游戲.它很簡單,

問題是:

把五個數(shù)字56789,放到[][][] * [][],令結(jié)果最大.

你最先對自己說: "這有什么難,把最大的放到最大位數(shù)那里就行了."你再心算了一下,也許不對.每個結(jié)果要看其他位置上放了什么數(shù)才行.你開始覺得有些興趣了,反正你正在學(xué)一種好玩的編程語言,何不練習(xí)一下呢?

於是你開出你心愛的Python,開始思考: "其實(shí)我要的是一個程式,我給它各種數(shù)字的組合,然后它自動幫我找出最大的一個.如果我傳入1,1,1,1,1和1,1,1,1,2,它會知道要算111 * 11和111 * 12,求出較大的是111 * 12并輸出這個組合以及其乘積.這個程式并不難嘛."

切換行號顯示

1# calc.py

2defcalc(seq):

3maximum =0

4max_item = []

5foriinseq:

6product = (i[0]*100+ i[1]*10+ i[2]) * (i[3]*10+ i[4])

7ifproduct > maximum:

8maximum = product

9max_item = i

10elifproduct == maximum:

11max_item +=','+i

12returnmax_item, maximum

13

14seq = [ [5,6,7,8,9], [5,6,7,9,8] ]

15max_item, maximum =calc(seq)

16print"Maximum

at", max_item,",product", maximum

你試了一下,

$python calc.py

Maximum at [5, 6, 7, 9, 8] ,product 90160

沒問題.現(xiàn)在你只要給出所有的排列即可.你打了幾行,覺得[5,6,8,7,9]這樣打太辛苦了,而且用i[0]*100 + i[1]*10 ...的方法好像太難看了,因此你有必要做一次修改.好,用字串吧. "56789",這樣輸入時較方便,而且int("567") *

int("89")要好看得多,也應(yīng)該快些.另外你也把程式改得更短,看起來像是個有經(jīng)驗(yàn)的人所寫.

切換行號顯示

1# calc.py

2defcalc(seq, where):

3maximum, max_item =0, []

4foriinseq:

5product =int(i[:where]) *int(i[where:])

6ifproduct > maximum:

7maximum, max_item = product, i

8elifproduct == maximum:

9max_item +=','+ i

10print"Maximum at", max_item,",product", maximum

11

12if__name__ =="__main__":

13seq = ["56789","56798"]

14where =3

15calc(seq,where)

嗯,好些了.那句ifname== "main"是為了將來你把calc.py做為模組來用時而設(shè)的.在別的程式中用import calc的話那幾行就不會運(yùn)行了.

現(xiàn)在你可以隨自己的意來解更普遍的問題,比如123放在[]*[][],或是1234567放在[][][][]*[][][]這樣的問法.現(xiàn)在你開始輸入排列了. "56789",

"56798", "56879", "56897", ..........沒多久你又覺得自己太愚蠢了,為什么不叫電腦程式自動產(chǎn)生這些無聊的排列呢? 56789一共有5!也就是120種排列方法呢!如果你想算123456789的話,用手輸入可能要用去一生的時間!!

於是你開始想如何產(chǎn)生排列的算法了.用循環(huán)就可以了,不過循環(huán)會產(chǎn)生重覆的組合,譬如555*55.但我們可以加些條件式進(jìn)去把重覆項(xiàng)拿走.於是你有了第一個程式解.

切換行號顯示

1#permute1.py

2defpermute(seq):

3result = []

4forainseq:

5forbinseq:

6forcinseq:

7fordinseq:

8foreinseq:

9ifa!=banda!=canda!=danda!=eand\

10b!=candb!=dandb!=eand\

11c!=dandc!=eandd!=e:

12result.append(''.join([a,b,c,d,e]))

13returnresult

14

15seq =list("56789")

16where =3

17thelist =permute(seq)

18importcalc

19calc.calc(thelist,where)

你小心地記著用''.join()的方法產(chǎn)生字串要比用a+b+c+d快,同時也認(rèn)為用import calc的方式會讓你更容易為不同的地方做些速度的微調(diào).你開始運(yùn)行程式了:

%python permute1.py

Maxmum at 87596 ,product 84000

你成功了.啊哈,你認(rèn)為可以貼到留言板上去領(lǐng)賞了.經(jīng)過一些考慮后,你覺得還是要做到更普遍的功能,就是讓用戶輸入排列多少個數(shù)字,怎樣分割.研究了一下程式,你覺得用循環(huán)好像無法達(dá)到要求,因?yàn)槟闶虑安⒉恢酪哦嗌賯€數(shù)字,因此你不知道要寫多少個循環(huán)才夠.面對這種情況,你好像只能用遞歸的方法了.

你知道如何求得,例如, 5個數(shù)字的排列:先挑一個數(shù),有五種選擇;當(dāng)選定了一個數(shù)之后挑第二個數(shù)時只剩下四個選擇,依此類推.因此五個數(shù)共有5*4*3*2*1共120個排列.當(dāng)你面對"56789"這五個數(shù)的排列問題時,你先挑出一個數(shù),例如6,那剩下的便是一個四個數(shù)字的排列問題了.就是說, 56789的排列可以簡化(或是簡單復(fù)雜化:p)成字頭為5的所有排列加上字頭為6的所有排列加字頭為7的所有排列加字頭為8的所有排列再加字頭為9的所有排列.想通了這點(diǎn),你決定用遞歸函數(shù)來寫程式,先依次在56789中選出5,然后把剩下的6789當(dāng)做是一個新的求四位數(shù)排列的問題再次調(diào)用函數(shù),以得到所有以5為字頭的排列;再選出6,剩下的5789調(diào)用函數(shù).而每次求6789或是5789的排列時再把它簡化成另一個求3個數(shù)字的排列問題,直到要求的排列只剩下一個數(shù).

以下就是你的函數(shù),不過你還不知道它到底是不是正確的,因?yàn)閷戇f歸函數(shù)很易出錯,因此你要先試一下.

切換行號顯示

1#permute2.py

2defpermute(seq):

3l =len(seq)

4ifl ==1:

5return[seq]

6else:

7res=[]

8foriinrange(len(seq)):

9rest = seq[:i] + seq[i+1:]

10forxinpermute(rest):

11res.append(seq[i:i+1] + x)

12returnres

13

14seq =list("1234")

15thelist =permute(seq)

16thelist = [''.join(x)forxinthelist ]

17printthelist

你運(yùn)行后得到以下的結(jié)果:

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

看來是正確的.但有沒有辦法再快一些呢?你想了半天,終於發(fā)現(xiàn)其實(shí)你不必等到l = 1的時候才有所動作,你可以在l = 2的時候就干些事了.因?yàn)槟阒纋 = 2的話,排列一定是[ [0,1], [1,0] ]的,這樣你起碼可以用些力氣幫電腦一把.當(dāng)然如果你把l = 3的排列也寫出來更好,但寫到l = 4或以上大可不必了.這種幫它一下的做法在程式優(yōu)化中的學(xué)名是unroll,你隱約記得是學(xué)過的.好,現(xiàn)在你有另一個程式了.

切換行號顯示

1#permute3.py

2defpermute(seq):

3l =len(seq)

4ifl <=2:

5ifl ==2:

6return[ seq, [seq[1], seq[0]] ]

7else:

8return[seq]

9else:

10res=[]

11foriinrange(len(seq)):

12rest = seq[:i] + seq[i+1:]

13forxinpermute(rest):

14res.append(seq[i:i+1] + x)

15returnres

16

17seq =list("12345")

18thelist =permute(seq)

19thelist = [''.join(x)forxinthelist ]

20printthelist

現(xiàn)在你可以正式測試了.你把permute3.py改了一下,以便可以從命令行取得數(shù)字以及分割方法.程式變成下面的樣子,同時你也對permute2.py做了相同的修改.

切換行號顯示

1#permute3.py

2defpermute(seq):

3l =len(seq)

4ifl <=2:

5ifl ==2:

6return[ seq, [seq[1], seq[0]] ]

7else:

8return[seq]

9else:

10res=[]

11foriinrange(len(seq)):

12rest = seq[:i] + seq[i+1:]

13forxinpermute(rest):

14res.append(seq[i:i+1] + x)

15returnres

16

17importsys, calc

18seq =list(sys.argv[1])

19where =int(sys.argv[2])

20thelist = [''.join(x)forxinpermute(seq) ]

21Print'Got',len(thelist),'items.'

22calc.calc(thelist,where)

你開始試行了.用time方式來看程式到底運(yùn)行了多長時間吧.

$ time python permute2.py 56789 3

Got 120 items.

Maximum at 87596 ,product 84000

real0m0.057s

user0m0.050s

sys0m0.000s

$ time python permute3.py 56789 3

Got 120 items.

Maximum at 87596 ,product 84000

real0m0.040s

user0m0.030s

sys0m0.010s

呵,不錯.修改了的就是快些.到了這個地步,你開始覺得好奇了.像求排列這樣一個常見的問題,不知道別人都是怎樣做的呢.也許應(yīng)該到網(wǎng)上去找找看,或者有一兩個已經(jīng)寫好的程式片斷可以抄的.你可不想弄錯一個原來己經(jīng)有標(biāo)準(zhǔn)答案的問題.把permute2.py貼上留言板或者會令自己看起來像一個三流的程式設(shè)計(jì)員,這可是你最不想見到的.於是你在網(wǎng)上到處搜尋.不過似乎都是以遞歸算法為主的,直至用了一些時間,你終於在ASPN:的網(wǎng)上程式碼收集站上看到了這一個片斷:

Getting th permutation

of a sequence ? Python recipes ? ActiveState Code

切換行號顯示

1# permute4.py

2defpermute(seq, index):

3seqc = seq[:]

4seqn = [seqc.pop()]

5divider =2

6whileseqc:

7index, new_index =divmod(index,divider)

8seqn.insert(new_index, seqc.pop())

9divider +=1

10return''.join(seqn)

作者聲稱這個算法的量級是O(n)的.你覺得難以置信,但不妨一試.由於你理解到這個函數(shù)每次只傳回排列中的某一項(xiàng),因此你寫了個小程式去驗(yàn)算它.

切換行號顯示

1# test.py

2frompermute4.pyimportpermute

3

4seq =list("1234")

5foriinrange(30):

6printpermute(seq, i),

試驗(yàn)一下:

$ python test.py

1234 1243 1324 1423 1342 1432 2134 2143 3124 41233142 4132 2314

2413 3214 4213 3412 4312 2341 2431 3241 4231 34214321 1234 1243

1324 1423 1342 1432

測試顯示這個函數(shù)沒問題.但它怎樣做到的呢?你研究了一下,每個不同的index值都傳回唯一的排列,而且大過n!的index會從頭來算起, divider每次都要增加一,列表的排法又是按商余數(shù)來重整.唉,不得要領(lǐng).嗨!管它呢.反正能用就行了.於是你修改permute4.py,加入一個新的函數(shù)求factorial,這樣就可以調(diào)用permute得到所有的排列.并進(jìn)行計(jì)時.你用了更多的數(shù)字,以便速度的差別更明顯些.

切換行號顯示

1# permute4.py

2defpermute(seq, index):

3seqc = seq[:]

4seqn = [seqc.pop()]

5divider =2

6whileseqc:

7index, new_index =divmod(index,divider)

8seqn.insert(new_index, seqc.pop())

9divider +=1

10return''.join(seqn)

11

12deffact(x):

13f =1

14foriinrange(1,x+1):

15f *= i

16returnf

17

18importsys, calc

19seq =list(sys.argv[1])

20where =int(sys.argv[2])

21n = fact(len(seq))

22thelist = [

permute(seq, i)foriinrange(n) ]

23print'Got',len(thelist),'items.'

24calc.calc(thelist,where)

$ time cpython permute3.py 1234567 4

Got 5040 items.

Maximum at 6531742 ,product 4846002

real0m0.461s

user0m0.440s

sys0m0.020s

$ time cpython permute4.py 1234567 4

Got 5040 items.

Maximum at 6531742 ,product 4846002

real0m0.389s

user0m0.370s

sys0m0.010s

哇!的確不是蓋的.很好,而且現(xiàn)在你知道了別人不知的新答案.就把它貼上去罷.就在你決定的時候按鈕之際,你到底猶豫了: "我對這個算法不是很了解,如果別人問起的話怎樣回答呢?這會讓我像個東抄西抄的小偷呢!不,要不我要明白它的原理,不然就自己做一個比它更好的."你覺得壯志無限.

但是現(xiàn)在已經(jīng)很晚,你要去睡了.無奈你在床上反覆地思考著更好的方法,你整個晚上都沒睡好.

待續(xù)......

第二天

第二天

你醒來第一件事,洗臉?biāo)⒀?編程愛好者并不一定和終日蓬頭垢面同義.然后呢,看看電視報紙,做些公益活動,今天是禮拜天嘛.廢話少說,終於你在電腦前坐下,登入了你喜愛的Slackware /RedHat/ Redflag / Mandrake / Debian /WindowsXP / Chinese2000 / DOS / Solaris/ AIX / Unicos / OSX [作者按:請依實(shí)際情況增刪,但千萬拜托不要把SCO也加進(jìn)來],這些都是Python能夠運(yùn)行的平臺.

你記起你以前學(xué)到遞歸時聽過的話:任何遞歸/回溯函數(shù)都可以還原成非遞歸形式的.於是你決定用你自己的方式一試.你默念著求排列的方法, 5個數(shù)取一個,剩下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]]))

17returnresult

18

19printpermute(list("12345"))

這個程式依次創(chuàng)建5, 4, 3, 2, 1個數(shù)的列表,每個都不包括之前被選的數(shù)字,然后把5個數(shù)合起來完成一種排列.當(dāng)然,你還有空間做unroll.但現(xiàn)在問題在於,你對程式的要求是事先并不知道要求多少個數(shù)字的排列,就是你不知道要寫幾個for才夠.但現(xiàn)在你認(rèn)為有一個好辦法:既然Python是動態(tài)的,它可以執(zhí)行自己寫出來的編碼,為什么不叫它自己幫自己來寫這個循環(huán)程式以完成工作呢?你覺得這種讓程式來為自己寫程式的想法很科幻也很妙,而且讓你記起了以前聽到很多資深程式員愛用的m4宏語言.於是你趕緊試了一個.你認(rèn)為可以用counter0, counter1,

counter2...來代替i, j, l, m...的循環(huán)子命名法.

切換行號顯示

1# permute5.py

2defgenfunc(n):

3head ="""

4def permute(seq0):

5result = [] """

6boiler ="""

7for counter%i in

seq%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)

15returnhead +'\nreturn result\n'

16

17importsys

18functext = genfunc(len(sys.argv[1]))

19printfunctext

20exec(functext)

21printdir()

22thelist = permute(list(sys.argv[1]))

23print'Got',len(thelist),'items.'

運(yùn)行一下,

sh-2.05b$ python permute5.py 12345 3

def permute(seq0):

result = []

for counter1in seq0:

seq1 =seq0[:]

seq1.remove(counter1)

forcounter2 in seq1:

seq2 =seq1[:]

seq2.remove(counter2)

forcounter3 in seq2:

seq3 = seq2[:]

seq3.remove(counter3)

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

看來格式是弄對了.現(xiàn)在算算運(yùn)行時間,會不會好些呢?也許會比以前更快,也許因?yàn)橐賵?zhí)行自己產(chǎn)生的程式而更慢,一切都要看實(shí)際的數(shù)據(jù)才能呢!你修改了permute5.py以便它能標(biāo)準(zhǔn)化地計(jì)算時間.你開始覺得import calc實(shí)在是挺聰明的設(shè)計(jì).

切換行號顯示

1# permute5.py

2defgenfunc(n):

3head ="""

4def permute(seq0):

5result = [] """

6boiler ="""

7for counter%i in

seq%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)

15returnhead +'\nreturn result\n'

16

17importsys, calc

18functext = genfunc(len(sys.argv[1]))

19#print functext

20exec(functext)

21thelist = permute(list(sys.argv[1]))

22print'Got',len(thelist),'items.'

23calc.calc(thelist,int(sys.argv[2]))

開始計(jì)時:

$ time cpython permute5.py 1234567 4

Got 5040 items.

Maximum at 6531742 ,product 4846002

real0m0.213s

user0m0.200s

sys0m0.010s

啊哈!那個什么量級O(n)的也被你打敗!!你覺得它的量級其實(shí)不是O(n),那只是對找一整個排列其中一個的時候才有用,要把整個排列都算出來的話還是要回到n!上的.

你非常自豪.但這也許是適當(dāng)?shù)臅r候提醒自己謙虛的妤處.既然都到了這個地步了,何不再走多一步,翻一下書看看,也許你找到的方法已經(jīng)早有別人發(fā)現(xiàn)了.果真是這樣的話,你,一個無知的白癡,到處大吹大擂自己的發(fā)明是會被笑話的.

於是你找出了封塵的電腦和數(shù)學(xué)教科書.找到了排列組合一章,開始細(xì)讀.終於你找到了這樣的一幅圖畫:

[4321]

[3421]

[321]< [3241]

[21] <[231]... [3214]

[213]...

[1] <

[321]...

[21] <[231]...

[213]...

書中寫到,要產(chǎn)生一個排列其實(shí)可以用這樣一個方法:

"先選一個數(shù)1,然后第二個數(shù)2可以放在1的前面或是后面.而每一個放法都會產(chǎn)生一個2位數(shù),對於每一個這樣的兩位數(shù),第三個數(shù)3,都可以放在它的前面,中間,或是最后;如此產(chǎn)生一個3位數(shù);而每一個3位數(shù),第4位數(shù)都可以插入到這3個數(shù)的任何一個空位中,如此類推.書中還列出了一個程式范例呢!并聲這個方法要和已知的最快的算排列的方法速度相若.

你急不可待地開始把書中的描述實(shí)現(xiàn).用Python,你很快又得到了一個全新的程式:

切換行號顯示

1# permute6.py

2defpermute(seq):

3seqn = [seq.pop()]

4whileseq:

5newseq = []

6new = seq.pop()

7#print "seq:",seq,'seqn', seqn ,'new', new

8foriinrange(len(seqn)):

9item = seqn[i]

10forjinrange(len(item)+1):

11newseq.append(''.join([item[:j],new,item[j:]]))

12seqn = newseq

13#print 'newseq',newseq

14returnseqn

15

16importsys, calc

17seq =list(sys.argv[1])

18where =int(sys.argv[2])

19thelist =permute(seq)

20print'Got',len(thelist),'items.'

21calc.calc(thelist,where)

測試結(jié)果如下:

$ time cpython permute6.py 1234567 4

Got 5040 items.

Maximum at 6531742 ,product 4846002

real0m0.167s

user0m0.150s

sys0m0.020s

哇塞!書中自有黃金屋咧!想不到這個才是最快的算法.你開始感到要擊敗這次的對手不是不件容易的事,而且現(xiàn)在已經(jīng)很晚了,你身心也都被疲倦所包圍著.你絕望地看著這個新的程式碼和它那美妙的結(jié)構(gòu),作出最后的嘗試:

待續(xù)...

守夜人

守夜人

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'

]

上面就是permute6.py產(chǎn)生的四位數(shù)字排列結(jié)果,你細(xì)心地反覆觀看,終於看出了一些端倪:其實(shí)所產(chǎn)生的排列是有一種對稱性的,第一個和最后一個是完全次序相反的,而第二個又和倒數(shù)第二個完全相反.利用這些對稱性,也許你可以把計(jì)算時間打個對折喲.而你研究了一下程式的實(shí)現(xiàn)方法后你發(fā)現(xiàn)只要改一行!就可以實(shí)現(xiàn)這樣的功能:就是第一行seqn = [ seq.pop() ]改成seqn = [

seq.pop()+seq.pop() ].這樣你就實(shí)現(xiàn)了只產(chǎn)生其中一半的排列,爾后你只要把這個列表中的元素都掉個就完成了整個排列.程式如下

切換行號顯示

1# permute7.py

2defpermute(seq):

3seqn = [ seq.pop()+seq.pop() ]

4whileseq:

5newseq = []

6new = seq.pop()

7#print

"seq:",seq,'seqn', seqn ,'new', new

8foriinrange(len(seqn)):

9item = seqn[i]

10forjinrange(len(item)+1):

11newseq.append(''.join([item[:j],new,item[j:]]))

12seqn = newseq

13#print 'newseq',newseq

14returnseqn

15

16importsys, calc

17seq =list(sys.argv[1])

18where =int(sys.argv[2])

19thelist =permute(seq)

20print'Got',len(thelist),'items.'

21printthelist

22#這個等一下再探討

23#calc.calc2(thelist,

where)

測試數(shù)據(jù)表示果然這個改良了的程式要比原來快了剛好一倍.這次應(yīng)該足夠了.但是要得到整個排列的話要把這半個列表重抄一次而且每個元素都要反過來: "1234" -> "4321".但是在Python之中的字串并沒有反序的函數(shù),因此你必須先把字串變成列表,再反過來,然而list.reverse()這個函數(shù)偏偏很討厭的不會傳回任何值(因?yàn)樗莍n-place的緣故),所以你要用i = list(item);

i.reverse; i =''.join(i);這個復(fù)雜的方法.你想了想,這個做法大概會把原來只做一半排列所省下來的時間都浪費(fèi)掉了.你思考半天,終於決定重寫calc.py部份以便直接利用已知的半個列表.

切換行號顯示

1# calc.py

2defcalc(seq, where):

3maximum, max_item =0, []

4foriinseq:

5product =int(i[:where]) *int(i[where:])

6ifproduct > maximum:

7maximum, max_item = product, i

8elifproduct == maximum:

9max_item +=','+i

10print"Maximum at", max_item,",product", maximum

11

12defcalc2(seq, where):

13maximum, max_item =0, []

14foriinseq:

15product =int(i[:where]) *int(i[where:])

16ifproduct > maximum:

17maximum, max_item = product, i

18elifproduct == maximum:

19max_item +=','+i

20rev =list(i)

21rev.reverse()

22i =''.join(rev)

23product =int(i[:where]) *int(i[where:])

24ifproduct > maximum:

25maximum, max_item = product, i

26elifproduct == maximum:

27max_item +=','+i

28print"Maximum at", max_item,",product", maximum

當(dāng)然你保留了以前的函數(shù)calc而只是新加一個專門給permute7.py調(diào)用的calc2函數(shù).你試了一下速度,成功了比permute6.py快了一丁點(diǎn).雖然只是這一點(diǎn)兒點(diǎn)兒,你也覺得快活無比.因?yàn)橛忠淮?你為一個大家都覺得好的方法做出了改良.

雖然你知道在這個階段如果你把calc.py整合到排列產(chǎn)生器中也許會得更好的提速效果,但你覺得現(xiàn)在這樣已經(jīng)可以很多人都認(rèn)同你的能力了.而且能把一個高效的排列產(chǎn)生器獨(dú)開來也許是聰明的做法,因?yàn)閷砟阋欢〞儆盟?你看了一下所有的程式,從permute1.py到permute7.py,再做了一次速度的檢定.反正是最后一次了,干脆做個大的吧.

$ time python permute2.py 123456789 5

Got 362880 items.

Maximum at 875319642 ,product 843973902

real0m46.478s

user0m46.020s

sys0m0.430s

$ time python permute3.py 123456789 5

Got 362880 items.

Maximum at 875319642 ,product 843973902

real0m38.997s

user0m38.600s

sys0m0.400s

$ time python permute4.py 123456789 5

Got 362880 items.

Maximum at 875319642 ,product 843973902

real0m33.845s

user0m33.460s

sys0m0.380s

$ time python permute5.py 123456789 5

Got 362880 items.

Maximum at 875319642 ,product 843973902

real0m10.681s

user0m10.530s

sys0m0.150s

$ time python permute6.py 123456789 5

Got 362880 items.

Maximum at 875319642 ,product 843973902

real0m8.279s

user0m8.110s

sys0m0.170s

$ time cpython permute7.py 123456789 5

Got 181440 items.

Maximum at 875319642 ,product 843973902

real0m7.827s

user0m7.650s

sys0m0.180s

嗯,很不錯.最快的要比原先快上近七倍呢!於是你打算明天一有空便把這個最好的公式貼到網(wǎng)上去,讓更多人分享.你很放心地去睡覺了.

但是不知為了什么,你總覺得有些事煩擾著你,還有什么不妥的地方呢?你實(shí)在想不到了,迷迷糊糊地抱著迷惑不安的心情入夢.

終於你忍不住爬了起床,再一次回到電腦屏幕前.你想到了一個致命的問題,對於很大很大的排列, permute7.py還是會嘗試一下子把所有的排列都做出來,不用多久電腦資源就會被耗光的.你也許要另想一個方法,每次只做一個排列.但你是否可以把所有的排列用1, 2, 3, 4的方法數(shù)出來呢?

你看著教科書上的那幅圖畫,這樣的樹狀結(jié)構(gòu)應(yīng)該有辦法的,你對自己說.

慢慢讀著書上的文字.設(shè)想有n個數(shù)字,先取第一個數(shù)字.再取第二個數(shù)字,第二個數(shù)可以放在第一個數(shù)的左或右面,就是有0, 1兩個選擇.再取第三個數(shù),放到前面選好的兩個數(shù)字中,可以放在最左,中間,最右,就是有0, 1, 2三個選擇.嗯,很自然嗎.忽然你想到了二進(jìn)位,八進(jìn)位那些數(shù)系轉(zhuǎn)換關(guān)系. "我可以設(shè)計(jì)這樣一個數(shù), ...xyz,其中個位數(shù)z是二進(jìn)位的,也就是放第二個數(shù)的兩個位置;十位數(shù)y是三進(jìn)位的,化表放第三個數(shù)字的三個位子,然后百位數(shù)是四進(jìn)位,千位數(shù)是五進(jìn)位的,依以類推."沒錯,這樣設(shè)計(jì)的話,如果0表示放於最左面的話,則"2021"這個數(shù)就代表了排列五個元素(abcde),取一個a,然后第二個b放在a的右面成ab,取c放到最右面成為abc,取d放到最左面成dabc;最后e放到中間去成為daebc.至於"2021"這個特別的設(shè)計(jì)的數(shù)可以用..+ x*4 + y*3 + z*2這樣的計(jì)算來映對到自然數(shù)的數(shù)列上去.

沒錯了,如求4個數(shù)的4! = 24個排列,第18個排列可以這樣求得, 18除2,余數(shù)是0,所以第二個數(shù)放在第一個數(shù)的左面;然后商9再除3,余數(shù)0,所以第三個數(shù)於在頭兩個數(shù)的最左;最后3除以4,余數(shù)是3,因此第四個數(shù)要放在前三個數(shù)的第4個空位,也就是最右面.利用這個方法,你就不必先求出整個排列才能開始計(jì)算.盡管這好像犧牲了時間,但省下了大量的空間.你完全可以算出1000個數(shù)的最大排列方法,縱使那可能要用去幾個月的運(yùn)算.你更高興的是用這個方法,你可以把整個計(jì)算拆開成為一個一個的部份:譬如說求10! = 3628800個排列,你大可以把1到1000000讓一部電腦做, 1000001到2000001讓另一部來做...大家的工作并不重覆,這等於實(shí)現(xiàn)并行運(yùn)算了!啊哈!妙極了!

忽然你靈光一閃,對了,這個不正是permute4.py的算法嗎!你昨天還久思不得其解呢,現(xiàn)在你已經(jīng)完全明白了.嗚,雖然這么好的算法原來不是你原創(chuàng)的,但是你仍然異常興奮.因?yàn)槟愕乃悸肪购湍切┐笈兓ハ辔呛?你漸漸記起了當(dāng)你還在玩DOS游戲機(jī)的年代,曾有個古怪的人向你吹噓過某個電腦撲克游戲中用了一個威力很大的洗牌法,多么的快而且公平,不必怕黑客們用已知的隨機(jī)數(shù)表來出千.現(xiàn)在你猜到了,那個算法很可能就是眼下這一個了.有52張牌,如果要預(yù)先算出52!個排列才能洗牌可真要命呢.

你覺得舒服多了,你整理了一下程式,打算把結(jié)果告訴大家.然而剛才的不安感又重新來襲.你再看了一次最后也應(yīng)該是最棒的程式,心中安慰自己道: "千萬不要跌進(jìn)低等程式員的的陷阱,他們瘋也似的不斷追求,郤從來不知道自己的目標(biāo),也不知道什么才是好.完美的設(shè)計(jì)不在于你無法添加新的功能,完美的設(shè)計(jì)是再也不能精簡現(xiàn)有的功能."你覺得permute7.py已迫近了這一個極限.但你內(nèi)心深處并沒有因此而舒坦開來,一種懸空的感覺自足下升起.也許是你太累了,于是者你決定閉目養(yǎng)神數(shù)分鐘再開始上網(wǎng),可惜你很快地迷迷糊糊地進(jìn)入了夢境.

待續(xù)...

終篇

終篇

你做了一個夢,夢中你看到阿凡提騎著他那出名的毛驢來到你面前并向你提出挑戰(zhàn): "除非你解答了我的難題,不然我的驢子會不停在你耳邊嘶叫令你無法睡好!問題是:

把數(shù)字56789放到

[][][]*[][]里

得出最大的的乘積....

你發(fā)出會心的微笑,正想祭出你的permute7.py之時忽然想起阿凡提是不可能懂得電腦編程的!你心中登時涼了一大截:阿凡提的方法一定不必用電腦算出所有的排列方法,并很快的得知答案的.隨著一聲震天的驢嘶,你驚醒了,發(fā)現(xiàn)原來你伏在電腦桌上睡去了,不小心壓著了鍵盤上的方向鍵而令你的電腦發(fā)出了痛苦的BEEP聲.

回想夢境,你打算暫時離開電腦,回到問題本身上來:怎樣才能"看"出最大的乘積呢?

你拿出紙筆,開始計(jì)算:

假設(shè)五個數(shù)為[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

這個可以寫成一個矩陣:

de

a1000100

b10010

c101

你這樣想到:在整個答案中, a帶來的貢獻(xiàn)是一個百位數(shù)加上一個十位數(shù),而d的貢獻(xiàn)是一個百位數(shù)加十位數(shù)加個位數(shù),因此d要比a更重要.要取得最大的積則一定要把56789中最大的9放在d的位置,然后是a,如此類推.

為了方便計(jì)算,你干脆用對數(shù)來記數(shù)100 = 10e2,用2來代表好了,因此:

d e

a3 2

b2 1

c1 0

計(jì)算每一行或列的和,把它稱為該數(shù)的基值,我們得到

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

咦? b和e的基值是一樣的,怎么辦!

你思考著: "啊哈!因?yàn)槲覀冇昧藢?shù),而log(1) = 0因此把b和e之間的微小分別給忽略了!"好吧,試把每個數(shù)都加大一個,得到:

d e

a4 3

b3 2

c2 1

這樣基數(shù)變成了: a = 7, b = 5, c = 3, d

= 9, e = 6.這些基數(shù)代表了該位置的重要性,可以按大小分予不同的數(shù)字.

好,按基數(shù)的大小來分配數(shù)字你得到了865 * 97.一對答案,喲!不一樣!正確解是875 * 96.哪里不對了呢?仔細(xì)分析下來,你發(fā)現(xiàn)b和e互換了.換的原因是這樣的:

b的貢獻(xiàn): b * d * 100 + b * e *

10?e的貢獻(xiàn): e * a * 100 + e * b * 10 + e * c

粗看的話e的貢獻(xiàn)要大一些,但因?yàn)槲覀儼?配給了d而8配給了a,因此最終的結(jié)果是b的實(shí)際貢獻(xiàn)要比e大.由於e和b的基數(shù)只相差在e * c這個個位數(shù)乘積上, d和a之間的分配結(jié)果把這個小的差異覆蓋掉了.

你考慮著: "要把這樣的覆蓋也算上去的話,也許可以做一個二階基數(shù).如b * d的基數(shù)是100,但是由於d的基數(shù)為9,那b的二階基數(shù)可以算成9,代表和b相關(guān)的是一個較為重要的數(shù);同樣e * a的基數(shù)是也是100但由於a的基數(shù)只是7,因此e的二階基數(shù)只是7而已.這樣就可以得出b要比e更重要了."

於是你有了一個想法:先寫出相關(guān)矩陣,然后計(jì)算每個數(shù)的基數(shù)和二階基數(shù),再進(jìn)行排序,當(dāng)兩個基數(shù)很接近時就用二階基數(shù)來判別哪個較重要.嗯,你覺得自己聰明極了,於是開始驗(yàn)算,但很快又發(fā)現(xiàn)其實(shí)b和e的二階基數(shù)原來也是一樣的!!大家都是15.也許我們要用一個三階基數(shù)才能分辨他們.

你又想了一些新的二階基數(shù)的定義,有些的確給出正確的答案,但你漸漸覺得這一切并不很妥當(dāng).因?yàn)榫退隳苡?jì)出56789,但是在更多的排列,如7位數(shù)甚至9位數(shù)的排列你怎樣保證答案也一定準(zhǔn)確呢,而兩個基數(shù)到底怎樣才算是比較接近呢?仔細(xì)審視你的方法,用對數(shù)來表示乃至直接相加來求所謂的基數(shù)統(tǒng)統(tǒng)都是即興的,毫不嚴(yán)謹(jǐn).或者要真正解決他們必需要把每一種情況都算進(jìn)來,而那樣做的話必然要計(jì)算n!那么多次!說到底還是要算排列的.

你有些失望,但暗中覺得松了一口氣,因?yàn)榈降资莗ermute7.py得到最后的勝利.你伸了一下懶腰,原來天都快亮了.這時你感到有些餓,便去拿了半個涼饅頭,沖了一些可可.你對著空空的螢光屏,靜靜地坐了大概十分鐘,然后答案進(jìn)入你的腦海,謎團(tuán)被解開了.

你的方法是求出所有位置的"重要性"(用你的語言就是求基數(shù)),然后依次把最大的數(shù)字分配給最重要的位置.但是位置的重要性是和其他位置糾纏在一起的,因此一次過算出所有位置的重要性必須考慮大量不同的組合排列,并不實(shí)際.

但是,我們其實(shí)可以每次只求第一個最大的基數(shù)的位置(abc*de的情況下最大的基數(shù)是d),這個最大的基數(shù)是沒有爭議的.當(dāng)求得這個位置時,干脆把最大的數(shù)字放到該位子上,然后再求一次基數(shù),找出接下來最大的位子,這個位子也是無可爭議的.如此一來,原來求5個數(shù)字的全排列成就簡化為5次簡單的回圈.一個求Factorial(n)的問題變成了n次循環(huán)!

啊哈!

你精神大好,從另一個角度切入:

假如5個數(shù)字一樣, 11111,最大的乘積只能是111 * 11,現(xiàn)在容許改大一個數(shù),改哪個會使結(jié)果最大?

211 * 11, 121 * 11, 112 * 11, 111 *

21, 111 * 12 ?答案是111 * 21,也就是d的位置.好,把d替換成9.

問題變成5個數(shù)字, 111 * 91,改一個數(shù)(除了9),改哪一個?

211 * 91, 121 * 91, 112 * 91, 111 *

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

依此類推,答案正正是875 * 96.

你重開電腦,很快地把新方法輸入程式,并改名為wise.py.

切換行號顯示

1defsolve(seq,where):

2n =len(seq)

3seq.sort()

4seq.reverse()

5table = [ []foriinrange(n) ]

6left, right = where, n - where

7leftr =long('1'*left)

8rightr =long('1'*right)

9flag=[]

10foritemin[int(x)forxinseq]:

11foriinrange(left):

12table[left-i-1] = (leftr +10**i) * rightr

13foriinrange(right):

14table[right-i+where-1] = leftr * (rightr +10**i)

15foriinflag:

16table[i] =0

17tablesorted = table[:]

18tablesorted.sort()

19maxindex = table.index(tablesorted[-1])

20ifmaxindex >= where:

21rightr = rightr + (item-1) *10**(right-maxindex+where-1)

22else:

23leftr = leftr + (item-1) *10**(left-maxindex-1)

24flag.append(maxindex)

25#print maxindex, leftr, rightr

26returnleftr, rightr

27

28importsys

29leftr, rightr =

solve(list(sys.argv[1]),int(sys.argv[2]))

30print"Maximum

at", leftr,rightr,',product', leftr*rightr

你驗(yàn)算了一下結(jié)果,完全正確!這時你好奇地再次time了一下程式的速度

$time python permute7.py 123456789 5

Got 181440 items.

Maximum at 875319642 ,product 843973902

real0m7.827s

user0m7.650s

sys0m0.180s

$ time python wise2.py 123456789 5

Maximum at 87531 9642 ,product 843973902

real0m0.042s

user0m0.010s

sys0m0.030s

哇!快了近兩百倍!當(dāng)然了.如果算更多位的排列會快更多,因?yàn)閣ise.py跳離了n!的限制.

你現(xiàn)在覺得舒服多了.你真的解了這個問題.你不再怕有人會寫出更快10倍的程式了.你既有了"聰明"的答案(軟解)來對付阿凡提和他的驢子,而在硬解方面,你也自信有世界第一流的排列產(chǎn)生器.你完全滿足了,你不再感到疲累,心中疑猶一掃而空.這時你身體感到一陣震栗但心中卻喜樂無窮,你第一次感受到了編程之道的洗禮.并且,你學(xué)會了所有程式大師都有的態(tài)度:我沒法用中文來形容,這種態(tài)度叫做"to hack".你知道只要你熟練并保持這種態(tài)度來面對生命中的難題,你很快就可以滿師出山了.

你最后一次瀏覽了一下你的程式碼,發(fā)現(xiàn)在wise.py中,其實(shí)每一個循環(huán)完成后,最重要的位置和最次要的位子都是不容爭議的,因此大可放心地替換兩個數(shù)字而不是一個,那程式可以再快一倍.不過你覺得現(xiàn)在己經(jīng)很夠了,你頗有禪機(jī)地自言自語道: "我已經(jīng)找到明月,再糾纏只下去只是妄執(zhí)於指月的手而已."你熟練地登出系統(tǒng)并關(guān)上電腦,你知道這次你可以真正安心地睡一覺了.

哎喲!天已亮了,今天是禮拜一,你要上班的.喔!又要被老板說上班一條蟲,下班一條龍......慘.......

全篇完.

檢討總結(jié)

檢討總結(jié)

一)在上面的故事中,我們看到了解決編程問題的五個方法.

把問題規(guī)范成一個普遍的形式,這樣更容易和別人交流以及找相關(guān)資料.

自己嘗試找答案.

在網(wǎng)上搜尋更好的答案.

想一個方法來打敗這個更好的答案.

翻查教科書或是文獻(xiàn),從基本開始思考有沒有最好的解.這些書能被選成教本一定有它的原因.

研究問題的特殊情況,也許會有別出心裁的巧妙方法.

二)故事中每個程式都只有二三十行大小,說明Python語言表達(dá)力強(qiáng)且語意很濃縮,做為快速開發(fā)或是測算自己的想法都是非常好的.

三) Python程式濃縮之余,它的語言也異常的清晰.回看上面的程式,你會發(fā)現(xiàn)它們?nèi)疾浑y明白.這說明Python程式更加容易維護(hù).

四)在故事中,我們有很大的篇幅是在討論方法而只有小部份是在描述Python的語言特性.這證明Python更適合用來教授編程的概念.事實(shí)上, Python的作者Guido和很多人都認(rèn)為Python是電腦教育的首選語言.教師可以讓學(xué)生靜靜地思考,學(xué)通運(yùn)算的法則;而不是上來就瘋狂地敲打鍵盤,并要記住一大堆電腦語言的古怪特徵.

五)整個故事圍繞於算法的改進(jìn)而較少碰到Python程式的優(yōu)化問題.也許在續(xù)集中(如果有的話),我們要嘗試一下在固定的算法及盡量少改動程式碼的條件下,提高Python程式的效率.我暫時想到的方法包括:

利用較新和較快的語法.如yield, generator.

用Python的自帶優(yōu)化選項(xiàng)以及內(nèi)建模組.

用第三方的擴(kuò)展模組,如Numpy, Scipy.

用編譯方式代替解釋,如freeze, py2exe.

用JIT類的方法,如Psyco.

用Thread,在多CPU的機(jī)器上平行運(yùn)算.

最后一樣要大改程式了,用C來做擴(kuò)展.

更有'to hack'感覺的,修改Python主干程式,加入像string.reverse()這樣的輔助函數(shù).

六)文中所用的測試硬件:

CPU:? ? Pentium III 866?RAM: 128 MB

文中所用的測試軟件:

Slackware? ? ? Linux: 9.0?Linux Kernel:2.4.2GCC:? ? ? 3.2.2

Python:修改過的2.1.3

七)啃涼饅頭對腦筋有幫助.

八)如果你能想到更好的方法,歡迎聯(lián)絡(luò)本人: