查看: 5001|回复: 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; }6 M) \# u9 s4 }9 w" s& ^5 ]
<>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++; / k' Z/ y' m# O+ u! x$ i6 C
<> 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; //说明未排列完% D5 N2 Z& k' `# m, J5 h0 M* n
<> int j=0; while(p[j++]>=p[i+1]); //找到第一个大于或等于倒序元素的数组元素 j-=1; 
/ X+ u7 N* F3 O0 ~<> temp=p[i+1]; //交换这两个元素 p[i+1]=p[j]; p[j]=temp;
" t4 z5 Z* f' |1 s! P: q" C: p) ]<> 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 [' [- ^7 z2 E3 T$ q( w$ j<>void output(int *p) { cout<<endl; for(int i=0;i<N;i++) cout<<p<<' ';
 I& C& b* ^5 I. z: o$ O8 _. V- R<>}