全排列

算法1 

一个经典的全排列算法zz2007-06-19 08:39设想有 n 个数字, 先取第一个数字. 再取第二个数字, 第二个数可以放在第一个数的左或右面, 就是有 0, 1 两个选择. 再取第三个数, 放到前面选好的两个数字中, 可以放在最左, 中间, 最右, 就是有 0, 1, 2 三个选择. 嗯, 很自然吗. 忽然你想到了二进位, 八进位那些数系转换关系。可以设计这样一个数, ...xyz, 其中个位数 z 是二进位的, 也就是放第二个数的两个位置; 十位数 y 是三进位的, 代表放第三个数字的三个位子, 然后百位数是四进位, 千位数是五进位的, 依以类推." 没错, 这样设计的话, 如果 0 表示放於最左面的话, 则 "2021" 这个数就代表了排列五个元素 (abcde), 取一个 a, 然后第二个 b 放在 a 的右面成 ab, 取 c 放到最右面成为 abc, 取 d 放到最左面成 dabc; 最后 e 放到中间去成为 daebc. 至於 "2021" 这个特别的设计的数可以用2*5+ 0*4 + 2*3 + 1*2 这样的计算来映对到自然数的数列上去。

如求 4 个数的 4! = 24 个排列, 第 18 个排列可以这样求得, 18 除 2, 余数是 0, 所以第二个数放在第一个数的左面; 然后商 9 再除 3, 余数 0, 所以第三个数於在头两个数的最左; 最后 3 除以 4, 余数是 3, 因此第四个数要放在前三个数的第 4 个空位, 也就是最右面。 

 

算法 2 

/*******************************/
 *定义循环左移函数
 *将str[0]依次后移到str[m]
 *******************************/
void chang(char str[],int m)  
 {
  int i,j;
  char temp=str[0];
  for (i=0;i<m;i++) str[i]=str[i+1];
  str[i]=temp;
 }
/*******************************/
 *从str[m]开始进行全排列
 *n 是要全排列的个数，在这里仅作为参数，
 *值不发生变化。“ABCD”中 n === 4
 *******************************/
void pai(char str[],int m,int n) /*定义全排列函数*/
{
 int k;
 void chang(char str[],int m);
 if (m<n)        /* 定 义 递 归 调 用 出 口  */
  {
   for (k=0;k<=m;k++)
    {
     pai(str,m+1,n);  /*递归调用*/
     chang(str,m); /*调用左移函数*/
    }
  }
 else printf("%s ",str); 
}



本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/lotus_zal/archive/2008/03/20/2200997.aspx