查看: 5037|回复: 8

输出一组数字的所有排列

字体大小: 正常放大

kampoo

85 主题	2 听众	400 积分

升级 33.33%

该用户从未签到

电梯直达

1^#

发表于 2005-12-29 14:29 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

输出一组数字的所有排列，最简单的算法是什么？

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

fewrains

0 主题	2 听众	27 积分

升级 23.16%

该用户从未签到

2^#

发表于 2006-1-1 13:15 |只看该作者 |招呼Ta 关注Ta

<

>递归,从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; }
/ \9 x7 J3 b8 `9 N' |, N3 H. U<>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++; 
; ~& _4 c" J* B<> if (p_dat==N_permutation) // 对列满输出， out_dat(); else permutation(); // 否则继续添加 p_dat--; flag=0; } } } void main() { permutation(); getch(); }[em07][em07][em07]

我也说一句

发表

使用道具举报

fewrains

0 主题	2 听众	27 积分

升级 23.16%

该用户从未签到

3^#

发表于 2006-1-1 13:16 |只看该作者 |招呼Ta 关注Ta

<

>前头要加上:
<

>#include <iostream> #include <conio.h> using namespace std;

我也说一句

发表

使用道具举报

fewrains

0 主题	2 听众	27 积分

升级 23.16%

该用户从未签到

4^#

发表于 2006-1-3 00:44 |只看该作者 |招呼Ta 关注Ta

<

>非递归实现，效率不错
<

>#include <iostream> #include <conio.h> #include <windows.h> using namespace std;
<

>void output(int *p); //输出函数 void permutation(int *p);//全排列函数
<

>int a[]={1,2,3,4,5,6,7,8,9,10,11};//待排列数组 int N=sizeof(a)/sizeof(int); //数组长度 int *p=a; //数组指针
<

>void main() { permutation(p); //调用全排列函数 output(p); //输出排列结果 getch(); }
<

>void permutation(int *p) { bool flag=false; //标志排列是否结束 int temp; //临时变量,用来交换数组元素
<

> while(1) { for(int i=0;i<N-1;i++) { flag=true; //如已排列完,falg为真
<

> if(p<p[i+1]) //如果发现第一个倒序的数组元素,p[i+1]被称为倒序元素 { flag=false; //说明未排列完
4 J0 }: R1 W' F$ x% [7 c<> int j=0; while(p[j++]>=p[i+1]); //找到第一个大于或等于倒序元素的数组元素 j-=1; 1 B5 F8 K- { S) I+ F4 e
<> temp=p[i+1]; //交换这两个元素 p[i+1]=p[j]; p[j]=temp;3 B0 u! Y& K V" q. z2 o! g
<> 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); //输出排列结果 } }5 N3 U: k, S, ^) u( Q' k, M
<>void output(int *p) { cout<<endl; for(int i=0;i<N;i++) cout<<p<<' ';
$ `! o H! z5 G4 o, S% W4 s. ?<>}