全排列算法原理和实现.doc

/index.php 全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以1, 2, 3, 4, 5为例说明如何编写全排列的递归算法。1、首先看最后两个数4, 5。 它们的全排列为4 5和5 4, 即以4开头的5的全排列和以5开头的4的全排列。由于一个数的全排列就是其本身，从而得到以上结果。2、再看后三个数3, 4, 5。它们的全排列为3 4 5、3 5 4、 4 3 5、 4 5 3、 5 3 4、 5 4 3 六组数。即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头的和3,4的全排列的组合.从而可以推断，设一组数p = r1, r2, r3, . ,rn, 全排列为perm(p)，pn = p - rn。因此perm(p) = r1perm(p1), r2perm(p2), r3perm(p3), . , rnperm(pn)。当n = 1时perm(p = r1。为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。算法如下：#include int n = 0; void swap(int *a, int *b) int m; m = *a; *a = *b; *b = m; void perm(int list, int k, int m) int i; if(k m) for(i = 0; i = m; i+) printf(%d , listi); printf(n); n+; else for(i = k; i m) 应该是if(k = m) 回复 引用 #6楼 2008-11-28 13:24 miao44未注册用户 优化了一下int perm(int list, int k, int m) int i; static int n;.swap(listk, listi); . swap(listk, listi); .return n; main()int list5=1,2,3,4,5;printf(total:%dn, perm(list, 0, 4); 这样就可以不用定义全局变量n,更友好。另外swap函数可以不用重写，直接使用系统函数，去掉前面的取址符就可以了。 回复 引用 #7楼 2009-03-14 14:35 YJC未注册用户 5楼的 你才错了 不是等号 是大于号 因为这里多一层 回复 引用 #8楼 2009-04-27 16:57 FC未注册用户 思想就是你说的这样,代码好像更好了点,献丑 #include void swap(char *a,char *b) char t; t = *a; *a = *b; *b = t; void print(char *a,int l) int i = 0; for(;il;+i) printf(%c,ai); printf(n); void permut(char * a,int p,int q,int length) int i = 0; for(i = p;i=q;+i) swap(&ai,&ap); if(p = q) print(a,length); permut(a,p+1,q,length); int main() char a4 = a,b,c,d; permut(a,0,3,4); return 0; 回复 引用 #9楼 2009-06-03 09:48 lll未注册用户 for循环中最后一个swap()好像没作用 回复 引用 #include #include using namespace :std;#define SIZE 6/字符的个数，因为末尾是0所以实际少一个int count=0;/控制输出的函数templatevoid Swap(T&a,T&b)/模板函数比较通用，交换a,b T temp=a; a=b; b=temp;templatevoid Prem(T list,int k,int m)/k是从该数组的第k个开始排，从第一个开始，到第m个结束，全排列的话k=0，m=size; int i; if (k=m)/当排到最后一个时，一次排列结束，输出这次的排列组合 count+; for (i=0;i=m;i+) coutlisti; coutt; if (count=6)/输出控制行，每行6个排列 coutendl; count=0; else for (i=k;im;i+) Swap(listk,listi); Prem(list,k+1,m);/使用递归实现 Swap(listk,listi); int main() string sSIZE=A,B,C,D,E;/实际