输出全排列方法

IA_Geek · 2019-02-17 15:19:46 · 个人记录

对于给定的集合A{a1,a2,...,an},其中的n个元素互不相同，如何输出这n个元素的所有排列（全排列）。

里以A{a,b,c}为例，来说明全排列的生成方法，##### ## 对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，……，依次类推，我们可以将集合的全排列与一棵多叉树对应。如下图所示

在此树中，每一个从树根到叶子节点的路径，就对应了集合A的一个排列。通过递归算法，可以避免多叉树的构建过程，直接生成集合A的全排列，复杂度O（n*n！）代码如下。

#include <iostream>
using namespace std;
const int maxn=1000;
int a[maxn];
void swap(int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void perm(int k,int m,int pk,int pm)//k,m一般取起始和终点位置，k是不断变化的
{
    //k是中间变量，m初始化为参与拍列元素的起始坐标和终止坐标
    //pk和pm分表表示参与排列元素的起始和终止坐标，不变的量。
    if(k==m){//当k换到最后的时候，便是出口，是已经交换好的序列
        for(int i=pk;i<=pm;i++) cout<<a[i];
        cout<<endl;
    }
    else{
        for(int i=k;i<=m;i++){
            swap(k,i);//一部分一部分的交换，最后进行还原
            perm(k+1,m,pk,pm);//模拟一下过程，一开始求解N确定一个元素后，求解N-1，依次类推。
            swap(k,i);//还原
        }
    }
}
int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
        a[i]=i;
    perm(1,x,1,x);
    return 0；

```#include <iostream>
using namespace std;
const int maxn=1000;
int a[maxn];
void swap(int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void perm(int k,int m,int pk,int pm)//k,m一般取起始和终点位置，k是不断变化的
{
    //k是中间变量，m初始化为参与拍列元素的起始坐标和终止坐标
    //pk和pm分表表示参与排列元素的起始和终止坐标，不变的量。
    if(k==m){//当k换到最后的时候，便是出口，是已经交换好的序列
        for(int i=pk;i<=pm;i++) cout<<a[i];
        cout<<endl;
    }
    else{
        for(int i=k;i<=m;i++){
            swap(k,i);//一部分一部分的交换，最后进行还原
            perm(k+1,m,pk,pm);//模拟一下过程，一开始求解N确定一个元素后，求解N-1，依次类推。
            swap(k,i);//还原
        }
    }
}
int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
        a[i]=i;
    perm(1,x,1,x);
    return 0；```c
#include <iostream>
using namespace std;
const int maxn=1000;
int a[maxn];
void swap(int i,int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}
void perm(int k,int m,int pk,int pm)//k,m一般取起始和终点位置，k是不断变化的
{
    //k是中间变量，m初始化为参与拍列元素的起始坐标和终止坐标
    //pk和pm分表表示参与排列元素的起始和终止坐标，不变的量。
    if(k==m){//当k换到最后的时候，便是出口，是已经交换好的序列
        for(int i=pk;i<=pm;i++) cout<<a[i];
        cout<<endl;
    }
    else{
        for(int i=k;i<=m;i++){
            swap(k,i);//一部分一部分的交换，最后进行还原
            perm(k+1,m,pk,pm);//模拟一下过程，一开始求解N确定一个元素后，求解N-1，依次类推。
            swap(k,i);//还原
        }
    }
}
int main()
{
    int x;
    cin>>x;
    for(int i=1;i<=x;i++)
        a[i]=i;
    perm(1,x,1,x);
    return 0；