layout: post
title: 排列组合算法的实现代码
categories:
2014-08-02 17:43:47
有些时候我们需要利用程序实现排列组合算法, 下面是我根据网上的代码改写的awk代码, 可实现排列或是组合, 当然元素数目不能太大.
排列
<pre class="line-numbers" data-start="0"><code class="language-bash"># 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--
}
}
'
</code></pre>组合
<pre class="line-numbers" data-start="0"><code class="language-bash"># 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
}
}
}
'
</code></pre>如果是在Python中, 就容易多了, 可参考下面的代码.
<pre class="line-numbers" data-start="0"><code class="language-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("\n")
for j in range (i+1, Nseq):
if seq[j]!="":
Nmat=0
for ii in range (n):
for jj in range (n):
if(seq[i][ii]==seq[j][jj]): Nmat += 1
if Nmat>=n-1:
seq[j]=""
# else:
# print " >", j, seq[j], Nmat
if(Ntot<18): print ">>>>", Nrnd, Ntot
fh.close()
</code></pre>网络资源