Perm全排列问题

水深无声 2022-01-06 00:41 214阅读 0赞

【**题目**】设计一个递归算法生成n个元素\{r1,r2,…,rn\}的全排列。

【**算法讲解**】

设R=\{r1,r2,…,rn\}是要进行排列的n个元素，Ri=R-\{ri\}。  
集合X中元素的全排列记为perm(X)。  
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。  
R的全排列可归纳定义如下：   
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；  
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。  
实现思想：将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

【**示例**】

当n=3，并且E=\{a，b，c\}，则：  
perm(E)=a.perm(\{b,c\}) + b.perm(\{a,c\}) + c.perm(\{a,b\})  
perm(\{b,c\})=b.perm(c) + c.perm(b)  
a.perm(\{b,c\})=ab.perm(c) + ac.perm(b)  
=ab.c + ac.b=(abc, acb)

![992501-20170403223134222-560535842.png][]

【**核心代码**】

![复制代码][copycode.gif]

template<class Type>
    void Perm(Type list[],  int k, int m )
    { //产生[list[k:m]的所有排列
        if(k==m)
         {  //只剩下一个元素
             for (int i=0;i<=m;i++) 
         cout<<list[i];
             cout<<endl;
        }
        else  //还有多个元素待排列，递归产生排列
           for (int i=k; i<=m; i++)
            {
               swap(list[k],list[i]);
               Perm(list,k+1,m);   
               swap(list[k],list[i]);         
             }
    }

![复制代码][copycode.gif]

【**完整代码**】

![复制代码][copycode.gif]

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    template<class Type>
    void Perm(Type list[],  int k, int m )
    { //产生[list[k:m]的所有排列
        if(k==m)
         {  //只剩下一个元素
             for (int i=0;i<=m;i++) 
         cout<<list[i];
             cout<<endl;
        }
        else  //还有多个元素待排列，递归产生排列
           for (int i=k; i<=m; i++)
            {
               swap(list[k],list[i]);
               Perm(list,k+1,m);   
               swap(list[k],list[i]);         
             }
    }
    
    int main() {
        
        char s[]="abc";
        Perm(s,0,2);
    
        return 0;
    }

![复制代码][copycode.gif]

转载于:https://www.cnblogs.com/apex-wzw/p/10425426.html

[992501-20170403223134222-560535842.png]: /images/20211228/a7c1b4cc2b1c40308a6a39ea21d22d8f.png
[copycode.gif]: /images/20211228/22067be41a4547ae82b7c01b5d48aaff.png