Chinaunix首页 | 论坛 | 博客
  • 博客访问: 52496
  • 博文数量: 25
  • 博客积分: 166
  • 博客等级: 入伍新兵
  • 技术积分: 177
  • 用 户 组: 普通用户
  • 注册时间: 2011-12-28 08:57
文章分类

全部博文(25)

文章存档

2015年(2)

2013年(1)

2012年(18)

2011年(4)

我的朋友

分类: C/C++

2012-05-15 21:44:08

http://blog.csdn.net/sunbingxi_/article/details/6125426

 #define N 3

   int a[N] = { 1, 2, 3 };    则打印出
1 2 3
1 3 2  2 1 3 2 3 1 3 2 1 3 1 2 1 2 3程序的主要思路是:
  1. 把第1个数换到最前面来(本来就在最前面),准备打印1xx,再对后两个数2和3做全排列。

  2. 把第2个数换到最前面来,准备打印2xx,再对后两个数1和3做全排列。

  3. 把第3个数换到最前面来,准备打印3xx,再对后两个数1和2做全排列。

    可见这是一个递归的过程,把对整个序列做全排列的问题归结为对它的子序列做全排列的问题,注意我没有描述Base Case怎么处理,你需要自己想。你的程序要具有通用性,如果改变了N 和数组a 的定义(比如改成4个数的数组),其它代码不需要修改就可以做4个数的全排列(共24种排列)。

    解题过程:

   (1) 当 N = 1的时候,则直接打印数列即可。

   (2) 当 N = 2的时候,设数组为 [a, b]

            打印a[0], a[1] (即a,b)

            交换a[0],a[1]里面的内容

            打印a[0],a[1]   (此时已变成了 [b, a] )

    (3) 当 N = 3的时候,数组为 [a, b, c]

  •  
    •  把a放在 a[0] 的位置(原本也是如此,a[0] = a[0]),打印b,c的全排列(即a[1], a[2]的全排列)

                       a  b  c

                       a  c  b

  •  
    •  把b放在a[0]的位置(这时候需要交换原数组的a[0]和a[1]),然后打印a, c的全排列

                       b   a  c

                       b   c  a                        

                  打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置

  •  
    •  把c放在a[0]的位置 (这时候需要交换的是原数组的a[0]和a[2]),然后打印a, b的全排列
             c  b  a              c  a  b 打印完后再换回原来的位置,即a还是恢复到a[0],b还恢复到a[1]的位置
至此,全排列完成
当 N = 4,5,6,……的时候,以此类推
[c-sharp] view plaincopy
  1. #include   
  2. #define N 3  
  3.   
  4. int a[N];  
  5.   
  6. void perm(int); /*求数组的全排列 */  
  7. void print();  
  8. void swap(intint);//交换前缀  
  9.   
  10. int main(){  
  11.     int i;  
  12.     //int offset;  /* 从第offset个数开始排列 */  
  13.     for(i = 0; i
  14.         a[i] = i + 97;  
  15.     }  
  16.     perm(0);  
  17. }  
  18.   
  19. void perm(int offset){  
  20.     int i, temp;  
  21.     if(offset == N-1){  
  22.         print();  
  23.         return;  
  24.     }else{  
  25.         for(i = offset;i < N; i++){  
  26.             swap(i, offset);//交换前缀  
  27.             perm(offset + 1);//递归  
  28.             swap(i, offset);//将前缀换回来,继续做前一次排列  
  29.         }  
  30.     }  
  31. }  
  32.   
  33. void print(){  
  34.     int i;  
  35.     for(i = 0; i < N; i++)  
  36.         printf(" %c ",a[i]);  
  37.     printf("/n");  
  38. }     
  39.   
  40. void swap(int i, int offset){  
  41.     int temp;  
  42.     temp = a[offset];  
  43.     a[offset] = a[i];  
  44.     a[i] = temp;  
  45. }  
如果再定义一个常量M 表示从N 个数中取几个数做排列(N == M 时表示全排列),原来的程序应该怎么改?
接替思路和递归做全排列大致相当,都是先把第一个数放到最前面,然后对后面的数进行排列。代码如下:
[c-sharp] view plaincopy
  1. #include   
  2. #include   
  3.   
  4. #define N 4  
  5. #define M 3  
  6.    
  7. int a[N];                  /* N个数 */  
  8. int temp[M];            /* 从N个数中选出的M个数 */  
  9.    
  10. void perm(intint);   /* 排列 */  
  11. void swap(intint);  /* 交换两个数 */  
  12. void print();             /* 打印 */  
  13.    
  14. int main(){  
  15.     int i;  
  16.     int start = 0;//起始位置  
  17.     int count = M;//排列到个数  
  18.     for(i = 0; i < N; i++){  
  19.         a[i] = i + 97;  
  20.     }  
  21.     perm(start, count);  
  22. }  
  23.    
  24. void perm(int offset, int count){  
  25.     int i;  
  26.     if( count == 0 ){  
  27.         print();  
  28.         return;  
  29.     }else{  
  30.         for(i = offset; i < N; i++){  
  31.             temp[offset] = a[i];  
  32.             move(offset, i);  
  33.             perm(offset+1, count-1);  
  34.             move(offset, i);  
  35.         }  
  36.     }  
  37. }  
  38.    
  39. void swap (int offset, int i){  
  40.     int another;  
  41.     another = a[offset];  
  42.     a[offset] = a[i];  
  43.     a[i] = another;  
  44. }  
  45.    
  46. void print(){  
  47.     int i;  
  48.     for(i = 0; i < M; i++)  
  49.         printf(" %c ",temp[i]);  
  50.     printf("/n");  
  51. }  
阅读(587) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~