博文

全排列输出算法

已有 2329 次阅读 2014-8-3 07:55 |个人分类:我的工具箱|系统分类:科研笔记|关键词:学者

下面的代码用于生成几个数据的全排列, 在有些时候需要用到, 当然元素个数不要太多.

# Language: bashawk ' BEGIN { Ndat=5;for(i=1; i<=Ndat; i++) p[i]=i;for(i=1; i<=Ndat; i++)printf("%3d", p[i])print "";while(1){NextPermut(Ndat, p)for(i=1; i<=Ndat; i++)printf("%3d", p[i])print "";}}functionNextPermut(Ndat, P){# 从后向前查找，看有没有后面的数大于前面的数的情况P(i-1)<Pi，# 若有则停在后一个数的位置。# 若没有后面的数大于前面的数的情况，说明已经到了最后一个排列，返回for(i=Ndat; i>0&& P[i-1]>P[i]; i--){if(i==2)exit;}Iend=i# 从后查到Iend，查找大于P(Iend-1)的最小的数，记入IbegIbeg=Iendfor(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=Ndatfor(i=Iend; i < j; i++){ tmp=P[j]; P[j]=P[i]; P[i]=tmp; j--}}'

参考