数学建模社区-数学中国

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

作者: kampoo    时间: 2005-12-29 14:29
标题: 输出一组数字的所有排列
输出一组数字的所有排列,最简单的算法是什么?
作者: fewrains    时间: 2006-1-1 13:15
<>递归,从VChelp的算法版主那里抄来的:</P>
' p8 M0 r: a# q9 w<><BR>#define  N_permutation 5 // 排列元素数量</P>
8 s# H5 Q- G5 h' j/ g* _& a2 Z<>unsigned char flag[N_permutation]; // 标记元素是否被使用<BR>unsigned char dat[N_permutation];  // 记录临时元素队列<BR>unsigned char p_dat=0;             // 对列指针</P>/ Z% Z4 ~. @% c; U6 r/ p
<>void out_dat()   // 输出对列dat中的内容<BR>{<BR> for(int i=0;i&lt;N_permutation;i++)<BR>  cout&lt;&lt;dat&lt;&lt;' ';<BR> cout&lt;&lt;endl;<BR>}</P>
4 M, M- V2 g2 V: b<>void permutation()          // 再入函数,生成N_permutation个字母的所有排列,<BR>{                           // 最大递归次数为N_permutation<BR> unsigned char i;           // 被再入函数入栈保护的局部变量<BR> for(i=0;i&lt;N_permutation;i++) <BR> {<BR>  if (flag==0)<BR>  {<BR>   flag=1;                // 标记元素被使用<BR>   dat[p_dat]=0x41+i;        // 将字母添加到队列<BR>   p_dat++;                  </P>- P8 e9 \5 w& c6 D4 {4 Z. O/ Q
<>   if (p_dat==N_permutation) // 对列满输出,<BR>    out_dat();<BR>   else permutation();       // 否则继续添加<BR>   p_dat--;<BR>   flag=0;<BR>  }<BR> } <BR>}<BR>void main()<BR>{<BR> permutation();<BR> getch();<BR>}</P>[em07][em07][em07]
作者: fewrains    时间: 2006-1-1 13:16
<>前头要加上:</P>$ W1 F, a& y7 {0 \. b& q7 |
<>#include &lt;iostream&gt;<BR>#include &lt;conio.h&gt;<BR>using namespace std;<BR></P>
作者: fewrains    时间: 2006-1-3 00:44
<>非递归实现,效率不错</P>
3 m9 Q! U1 V4 r  [' e2 _<>#include &lt;iostream&gt;<BR>#include &lt;conio.h&gt;<BR>#include &lt;windows.h&gt;<BR>using namespace std;</P>: d: G) c- s1 J0 [! x( ^5 `
<>void output(int *p);     //输出函数<BR>void permutation(int *p);//全排列函数</P>
. \+ \: ^/ {1 L' A: P$ ?<>int a[]={1,2,3,4,5,6,7,8,9,10,11};//待排列数组<BR>int N=sizeof(a)/sizeof(int);      //数组长度<BR>int *p=a;                         //数组指针</P>
1 K( K7 I1 F; U6 |' r. n<>void main()<BR>{<BR> permutation(p);    //调用全排列函数<BR> output(p);         //输出排列结果<BR> getch();<BR>}</P>, u" m) B6 E- I4 H0 a. R
<>void permutation(int *p)<BR>{<BR> bool flag=false;   //标志排列是否结束<BR> int temp;          //临时变量,用来交换数组元素</P>
# }0 U! B  G' f7 S2 {6 m<> while(1)<BR> {<BR>  for(int i=0;i&lt;N-1;i++)<BR>  {<BR>   flag=true;     //如已排列完,falg为真</P>. ]8 v, @4 G2 _7 @6 I
<>   if(p&lt;p[i+1]) //如果发现第一个倒序的数组元素,p[i+1]被称为倒序元素<BR>   { <BR>    flag=false; //说明未排列完</P>. O1 g( V1 W' `0 @& K/ ~: s- H
<>    int j=0;<BR>    while(p[j++]&gt;=p[i+1]); //找到第一个大于或等于倒序元素的数组元素<BR>    j-=1;                  </P>+ |$ w9 F4 A+ |8 f3 S
<>    temp=p[i+1];           //交换这两个元素<BR>    p[i+1]=p[j];<BR>    p[j]=temp;</P>
+ B. W+ G  A& m% Z<>    j=0;<BR>    while(j&lt;(i+1)/2)       //倒置倒充元素原位置以前的所有元素<BR>    {<BR>     temp=p[j];<BR>     p[j]=p[i-j];<BR>     p[i-j]=temp;<BR>     <BR>     j++;<BR>    }    <BR>    break;                 //跳出for循环,<BR>   }<BR>  }<BR>  if(flag)                       //如果排列完,结束循环<BR>   break;<BR>  //output(p);                        //输出排列结果<BR> }<BR>}</P>
7 L# I; ~+ I8 [2 P: ]6 T  }4 i# D<>void output(int *p)<BR>{<BR> cout&lt;&lt;endl;<BR> for(int i=0;i&lt;N;i++)<BR>  cout&lt;&lt;p&lt;&lt;' ';</P>' q9 p+ r- V5 i4 f) Z& L% w. j
<>}<BR></P>
作者: dsg333    时间: 2006-2-19 05:16
还有吗?
作者: zhouming09    时间: 2006-3-6 17:01
太高深了 不东
作者: zansan    时间: 2006-5-7 19:49
<p>&nbsp;<font color="#000000" size="+0">递归容易明白,就是慢,这个算法就是好.找到"倒置位"后进行倒置.</font></p>
作者: jinfly4997    时间: 2006-8-11 20:22
matlab里面好像有这个函数,我用过,但现在实在是既不起来了,你可以寻求帮助,但如果英语不太好,建议买一本参考教材看看相关命令,或者上网查一些有关命令的资料下载就是了,我的大部分matlab知识就是寻求网上帮助获得的,你也可以试试!
作者: sjian2001    时间: 2006-10-21 22:16
看过一篇文章是这么说的:<br/>比如说求1,2,3的全排列,<br/>先是{  1  }<br/>然后用2,在元素里所有空当插入<br/>变成了{ 21  , 12}<br/>然后用3,在元素里所有空当插入<br/>{321,231,213,312,132,123}<br/>算法还是好实现的。<br/>不知道跟其他算法有什么效率差别。<br/>




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