有些時候我們需要利用程序實現排列組合算法, 下面是我根據網上的代碼改寫的awk代碼, 可實現排列或是組合, 當然元素數目不能太大.

排列

# Language: bash awk ' BEGIN { Ndat=3 for(i=1; i<=Ndat; i++) {P[i]=i} YesDone=0 while(!YesDone) { for(i=1; i<=Ndat; i++) printf"%d ", P[i] print "" NextPermut(Ndat, P) } } function NextPermut(Ndat, P) { if (Ndat==0) {YesDone=1; return} # 從后向前查找，看有沒有后面的數大于前面的數的情況P(i-1)<Pi，若有則停在后一個數的位置。 # 若沒有后面的數大于前面的數的情況，說明已經到了最后一個排列，返回 for(i=Ndat; i>0 && P[i-1]>P[i]; i--) { } Iend=i if(Iend==1) { YesDone=1; return } # 從后查到Iend，查找大于P(Iend-1)的最小的數，記入Ibeg Ibeg=Iend for (i=Ndat; i>=Iend; i--) { if (P[Iend-1]< P[i] && P[i]< P[Ibeg]) Ibeg=i } #交換p[Ibeg]和p[Iend-1] tmp=P[Ibeg]; P[Ibeg]=P[Iend-1]; P[Iend-1]=tmp #倒置p[Iend]到p[Ndat] j=Ndat for(i=Iend; i< j; i++) { tmp=P[j]; P[j]=P[i]; P[i]=tmp j-- } } '

組合

# Language: bash awk ' BEGIN { m=6; n=4; a[1]="A"; a[2]="B"; a[3]="C"; a[4]="D"; a[5]="E"; a[6]="F" Comb(m,n) #RecComb(m, n, 1, n) } function RecComb(m, n, start, count, i,j) { # 遞歸實現 for(i=start; i<=m+1-count; i++) { b[count]=i if(count>1) RecComb(m, n, i+1, count-1); else { for(j=n; j>0; j--) printf("%s ",a[b[j]]); print "" } } } function Comb(m, n) { # 非遞歸 idx=1 p[idx]=1 #取第一個元素 while(1) { if(p[idx]>m) { #取到底了，回退 if(idx==1) break #各種情況取完了，不能再回退了 idx-- #回退到前一個 p[idx]++ #替換元素 } else if(idx==n) { #取夠了，輸出 for(i=1; i<=m; i++) printf("%s ", a[p[i]]) print "" p[idx]++ #替換元素 } else { #多取一個元素 idx++ p[idx]=p[idx-1]+1 } } } '

如果是在Python中, 就容易多了, 可參考下面的代碼.

# Language: python import copy import random import itertools n=6 seqIni=list(itertools.combinations('ABCDEFGHIJ', n)) Nseq=len(seqIni) print Nseq fh = open("Comb", "w") for i in seqIni : k=' '.join([str(j) for j in i]) fh.write(k+"\n") fh.close() for Nrnd in range (1): seq=copy.deepcopy(seqIni) if Nrnd==1: tmp=seq[1] seq[1]=seq[Nseq-1] seq[Nseq-1]=tmp if(Nrnd>1): random.shuffle(seq) # s="%d"%(Nrnd) # fh = open("Comb"+s, "w") # for i in seq : # k=' '.join([str(j) for j in i]) # fh.write(k+"\n") # fh.close() Ntot=0 for i in range (Nseq): if seq[i]!="": Ntot += 1 # if(Ntot>17): # print Ntot, seq[i] # fh.write("%d "%(Ntot)) # for kk in seq[i] : # k=' '.join([str(jk) for jk in kk]) # fh.write(k+" ") # fh.write("

總結

以上是生活随笔為你收集整理的排列组合算法的实现代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。