数学建模社区-数学中国

标题: 输出一组数字的所有排列 [打印本页]

作者: kampoo 时间: 2005-12-29 14:29
标题: 输出一组数字的所有排列
输出一组数字的所有排列，最简单的算法是什么？

作者: fewrains 时间: 2006-1-1 13:15
<

>递归,从VChelp的算法版主那里抄来的:
<

> #define N_permutation 5 // 排列元素数量
<

>unsigned char flag[N_permutation]; // 标记元素是否被使用 unsigned char dat[N_permutation]; // 记录临时元素队列 unsigned char p_dat=0; // 对列指针
<

>void out_dat() // 输出对列dat中的内容 { for(int i=0;i<N_permutation;i++) cout<<dat<<' '; cout<<endl; }; _$ _& E% ^& ^- }
<>void permutation() // 再入函数，生成N_permutation个字母的所有排列, { // 最大递归次数为N_permutation unsigned char i; // 被再入函数入栈保护的局部变量 for(i=0;i<N_permutation;i++) { if (flag==0) { flag=1; // 标记元素被使用 dat[p_dat]=0x41+i; // 将字母添加到队列 p_dat++; ) R) U2 s% h N( f# U, i3 Z6 I
<> if (p_dat==N_permutation) // 对列满输出， out_dat(); else permutation(); // 否则继续添加 p_dat--; flag=0; } } } void main() { permutation(); getch(); }[em07][em07][em07]
作者: fewrains 时间: 2006-1-1 13:16
<>前头要加上:5 [( ?( y7 g6 a
<>#include <iostream> #include <conio.h> using namespace std; 
作者: fewrains 时间: 2006-1-3 00:44
<>非递归实现，效率不错% v1 x8 c: t1 a
<>#include <iostream> #include <conio.h> #include <windows.h> using namespace std;
+ e8 c' p! o3 i; o6 G" R+ b: ~<>void output(int *p); //输出函数 void permutation(int *p);//全排列函数
) N$ k: B' ~' h' V; D8 x. h<>int a[]={1,2,3,4,5,6,7,8,9,10,11};//待排列数组 int N=sizeof(a)/sizeof(int); //数组长度 int *p=a; //数组指针
1 B3 E( d/ t8 H) ]1 q<>void main() { permutation(p); //调用全排列函数 output(p); //输出排列结果 getch(); }
/ ~- F5 y- g+ m7 R" n<>void permutation(int *p) { bool flag=false; //标志排列是否结束 int temp; //临时变量,用来交换数组元素- p' o( A, `9 [. {. o
<> while(1) { for(int i=0;i<N-1;i++) { flag=true; //如已排列完,falg为真8 ~/ l7 ?8 l+ c3 @. ]2 l
<> if(p<p[i+1]) //如果发现第一个倒序的数组元素,p[i+1]被称为倒序元素 { flag=false; //说明未排列完% \+ C9 |2 ]/ j) }& N1 I
<> int j=0; while(p[j++]>=p[i+1]); //找到第一个大于或等于倒序元素的数组元素 j-=1; 
' a9 W. r. O+ [0 u$ f6 b<> temp=p[i+1]; //交换这两个元素 p[i+1]=p[j]; p[j]=temp;; A* h( b, a5 I2 s$ y3 M, I7 y
<> j=0; while(j<(i+1)/2) //倒置倒充元素原位置以前的所有元素 { temp=p[j]; p[j]=p[i-j]; p[i-j]=temp; j++; } break; //跳出for循环, } } if(flag) //如果排列完,结束循环 break; //output(p); //输出排列结果 } }
2 ^' D3 m; |0 m3 q1 N% z<>void output(int *p) { cout<<endl; for(int i=0;i<N;i++) cout<<p<<' ';
: @6 D, I* X# O* c3 b/ c<>} 
作者: dsg333 时间: 2006-2-19 05:16
还有吗？
作者: zhouming09 时间: 2006-3-6 17:01
太高深了不东
作者: zansan 时间: 2006-5-7 19:49
 递归容易明白,就是慢,这个算法就是好.找到"倒置位"后进行倒置.
作者: jinfly4997 时间: 2006-8-11 20:22
matlab里面好像有这个函数，我用过，但现在实在是既不起来了，你可以寻求帮助,但如果英语不太好，建议买一本参考教材看看相关命令，或者上网查一些有关命令的资料下载就是了，我的大部分matlab知识就是寻求网上帮助获得的，你也可以试试！
作者: sjian2001 时间: 2006-10-21 22:16
看过一篇文章是这么说的： 比如说求1，2，3的全排列， 先是{ 1 } 然后用2，在元素里所有空当插入 变成了{ 21 , 12} 然后用3，在元素里所有空当插入 {321,231,213,312,132,123} 算法还是好实现的。 不知道跟其他算法有什么效率差别。 

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5