Liny_@NotePad

沉迷ACG中

递归求全排列

YOYO posted @ 2009年4月29日 08:00 in 【算法】与【数据结构】 with tags 递归 全排列 , 3044 阅读

 其实它是没有排序的全排列……

  1. #include<iostream>
  2. using namespace std;
  3.  
  4. #define N 30
  5.  
  6. /********************************
  7. * 打印数组函数
  8. ********************************/
  9. void printArray(int A[], int n){
  10.         for(int i=0; i<n; i++){
  11.                         cout<<A[i]<<" ";
  12.                 }
  13.         cout<<endl;
  14. }
  15.  
  16. /********************************************
  17. * 全排列算法
  18. *
  19. * 输入:数组A[],数组的元素个数n,
  20. *       当前递归层次已完成排列的元素个数k(0<=k<n)
  21. * 输出:数组A[]的全排列
  22. ********************************************/
  23. void perm(int A[], int n, int k){
  24.         if(k==n-1){                    //   已完成排列则打印
  25.                 printArray(A,n);
  26.         }else{
  27.                 for(int i=k; i<n ;i++){ //       生成后续的一系列排列
  28.                         swap(A[i], A[k]);
  29.                         perm(A, n, k+1);
  30.                         swap(A[i], A[k]);
  31.                 }
  32.         }
  33. }
  34.  
  35. int main(){
  36.         int A[N], n;
  37.  
  38.         cout<<"请输入数组的元素个数:";
  39.         cin>>n;
  40.  
  41.         cout<<"请输入数组的元素:";
  42.         for(int i=0; i<n; i++){
  43.                 cin>>A[i];
  44.         }
  45.  
  46.         cout<<"数组的全排列是:"<<endl;
  47.         perm(A,n,0);
  48.  
  49.         return 0;
  50. }

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter