当前位置:编程学习 > C/C++ >>

C++实现全排列

问题描述:
       有n个元素,我们的目的是生成这n个元素的全排列。
算法设计思路:
     (1)将规模为n的排列问题转化为规模为n-1的排列问题;
     (2)将规模为n-1的排列问题转化为规模为n-2的排列问题;
     (3)以此类推。
针对具体问题可以这么理解:(这里假设a[ ]={1,2,3,4,.....})
     (1)如果n=1,很显然,n的全排列为{1};
     (2)如果n=2,即a[]={1,2},n的全排列为
              {2,1}——>a[1]和a[2]交换,再求{2}的全排列,即归于步骤1;
              {1,2}——>a[2]和a[2]交换,再求{1}的全排列,即归于步骤1;
    (3)如果n=3,即a[]={1,2,3},n的全排列为
             {{3,2},1}——>a[1]和a[3]交换,再求{3,2}的全排列,即可归于步骤2;
             {{1,3},2}——>a[2]和a[3]交换,再求{1,3}的全排列,即可归于步骤2;
             {{1,2},3}——>a[3]和a[3]交换,再求{1,2}的全排列,即可归于步骤2;
       ......
       以此类推。
代码如下:
 
#include <iostream>  
  
using namespace std;  
  
int n;  
int sum=0;  
//数据互换  
void swap(int *a,int *b){  
    int temp;  
    temp=*a;  
    *a=*b;  
    *b=temp;  
}  
//输出结果  
void result(int a[]){  
    sum++;  
    cout<<sum<<endl;  
    for(int i=0;i<n;i++){  
        cout<<a[i];  
    }  
    cout<<endl;  
}  
//实现全排列核心算法  
void Perm(int a[],int n){  
    int i;  
    if(n==1){  
        result(a);  
    }  
    else{  
        for(i=0;i<n;i++){  
            swap(a[i],a[n-1]);  
            Perm(a,n-1);  
            swap(a[i],a[n-1]);  
        }  
    }  
}  
//主函数  
int main(){  
    int a[101];  
    cin>>n;  
    for(int i=0;i<n;i++){  
        cin>>a[i];  
    }  
    Perm(a,n);  
    return 0;  
}  

 

 
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,