全排列的那些事儿

分手后的思念是犯贱 2023-07-23 03:56 7阅读 0赞

### 全排列的那些事儿 ###

*   *  大佬们的写的很好：
     *  next\_permutation实现：
     *  递归实现：
     *  去重全排列：
     *  打印n个数中任意m个数的全排列：

## 大佬们的写的很好： ##

[全排列1][1]  
[全排列2][2]  
[全排列3][3] 这第三个链接里去重全排列那一块儿的去重似乎不太对，可以考虑下面我的思考与实现  
类似于这位大佬的实现：[全排列4][4]

## next\_permutation实现： ##

（从小到大按字典序输出下一个排列）

#include <iostream>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
        
        int data[4] = {
        5, 2, 1, 4};
        sort(data,data+4);
        do{
        
            for(int i=0; i<4; i++){
        
                cout<<data[i]<<" ";
            }
            cout<<endl;
        }while(next_permutation(data,data+4));
    
        return 0;
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]

## 递归实现： ##

#include <iostream>
    
    using namespace std;
    #define Swap(a,b){int temp=a; a=b; b=temp;}  //交换
    
    int data[] = {
        1,3,5,7};
    int num = 0;
    
    void Perm(int begin, int end)
    {
        
        int i;
        if(begin == end){
          //递归结束，产生一个全排列（一个叶节点）
            for(int j=0; j<3; j++){
          //打印全排列
                cout<<data[j]<<" ";
            }
            cout<<data[3]<<endl;
            num++;  //统计全排列个数
        }else  //没到叶节点就递归下去
            for(i = begin; i<=end; i++){
        
                Swap(data[begin],data[i]);  //八当前的第i个数与后面的所有数交换位置
                Perm(begin+1,end);
                Swap(data[begin],data[i]);  //恢复上一级，用于下一次交换
            }
    
    }
    
    int main()
    {
        
        Perm(0, 3);
        cout<<"全排列的个数："<<num<<endl;
        return 0;
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]

## 去重全排列： ##

如果数列中有重复的，比如1，3，5，5，7，此时该如何计算全排列呢？只需要去重即可。

#include <iostream>
    
    using namespace std;
    #define Swap(a,b){int temp=a; a=b; b=temp;}  //交换
    
    int data[] = {
        1,3,3,7};
    int num = 0;
    
    bool isEqual(int k,int m)   //去重函数
    {
        
        for(int i=k; i<m; i++)   //判断a[k]到a[m-1]是否有与a[m]相同的元素，若存在，返回false
        {
        
            if(data[i] == data[m])
                return false;
        }
        return true;
    }
    void Perm(int begin, int end)
    {
        
        int i;
        if(begin == end)   //递归结束，产生一个全排列（一个叶节点）
        {
        
    
            for(int j=0; j<3; j++)   //打印全排列
            {
        
                cout<<data[j]<<" ";
            }
            cout<<data[3]<<endl;
            num++;  //统计全排列个数
        }
        else   //没到叶节点就递归下去
            for(i = begin; i<=end; i++)
            {
        
                if(isEqual(begin,i))
                {
        
                    Swap(data[begin],data[i]);  //八当前的第i个数与后面的所有数交换位置
                    Perm(begin+1,end);
                    Swap(data[begin],data[i]);  //恢复上一级，用于下一次交换
                }
            }
    
    }
    
    int main()
    {
        
        Perm(0, 3);
        cout<<"全排列的个数："<<num<<endl;
        return 0;
    }

## 打印n个数中任意m个数的全排列： ##

只需要将begin == end的判断改为 begin == m  
如下：在数组中任取3个数的全排列只需：、  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2]

[1]: https://blog.csdn.net/axiqia/article/details/50967863
[2]: https://blog.csdn.net/fern_girl/article/details/70339961
[3]: https://blog.csdn.net/zhuchuanliang/article/details/81109805
[4]: https://blog.csdn.net/qq_40986486/article/details/103744997
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70]: /images/20230528/cc95fadc2c6a49da92b1e072e845ef1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 1]: /images/20230528/bc15014949a14a0c8a71c44237575a47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NDk3NDIz_size_16_color_FFFFFF_t_70 2]: /images/20230528/0ff0170eff9644038c391d5dd6401d4b.png