排列和组合问题完全解析

逃离我推掉我的手 2022-06-16 08:53 179阅读 0赞

排列和组合问题的本质区别在于，排列问题重在顺序，先选择谁再选择谁，组合问题重在选哪些元素，选择或者不选择。

### 一、排列问题 ###

给定一个包含 n 个元素的集合，有两个问题，一个是求全排列，即 n 个元素的全部排列顺序；另一个问题是求这 n 个元素中的 m 个元素的所有排列情况。

#### 1. 全排列问题 ####

首先给出下面程序中经常调用的交换函数代码：

#include <iostream>
        #include <vector>
        #include <algorithm>
        using namespace std;
        void swap(int &a, int &b){
            int temp = a;
            a = b;
            b = temp;
        }

（1）n各元素各不相同的情况

**思路：** 排列问题重在顺序，那么先考虑第一个选择的元素应该选择谁，应该考虑分别选择n个元素中的每一个元素，然后剩下的n-1个元素又是一个全排列的子问题，因此可以采用递归的方式来解决。

代码：

void printAllPermutation_withRepeat(int a[],int beg, int end,int n){
            if(beg >= end){
                for(int i=0;i<n;i++){
                    cout << a[i];
                }
                cout << endl;
                return;
            }
            for(int i=beg;i<=end;i++){
                swap(a[beg], a[i]);
                printAllPermutation_withRepeat(a, beg+1, end, n);
                swap(a[beg], a[i]);
            }
        }
        void test1(){
            int n;
            while(cin>>n){
                int a[n];
                for(int i=0;i<n;i++){
                    cin >> a[i];
                }
                printAllPermutation_withRepeat(a, 0, n-1, n);
            }
        }
        int main(){
            test1();
            return 0;
        }

测试：

> 3  
> 1 2 3

结果：

> 123  
> 132  
> 213  
> 231  
> 321  
> 312

这个只考虑了n个元素各不相同的情况，如果出现了相同的元素，结果中就会出现重复的排列，比如：

测试：

> 3  
> 1 2 2

结果：

> 122  
> 122  
> 212  
> 221  
> 221  
> 212

出现了大量重复，下面考虑如何改进上面结果出现重复的全排列。

（2）结果不允许重复的全排列

**思路：**比如3个元素 1 2 2，当 1 和第一个 2 交换后顺序为 2 1 2，会生成两个全排列 212 和 221；当 1 和第二个 2 交换后顺序为 2 2 1， 会生成两个全排列 221 和 212，可以看到如果当 1 和第二个 2 交换时加入判断，看看之前是否有和 2 做过交换，如果做过那么这次就不用再交换了，那么就不会出现重复了。

代码：

void printAllPermutation(int a[],int beg, int end,int n){
            if(beg >= end){
                for(int i=0;i<n;i++){
                    cout << a[i];
                }
                cout << endl;
                return;
            }
            for(int i=beg;i<=end;i++){
                bool flag = true;
                for(int j=i-1;j>=beg;j--){
                    if(a[j] == a[i]){
                        flag = false;
                    }
                }
                if(flag){
                    swap(a[beg], a[i]);
                    printAllPermutation(a, beg+1, end, n);
                    swap(a[beg], a[i]);
                }
            }
        }
        void test2(){
            int n;
            while(cin>>n){
                int a[n];
                for(int i=0;i<n;i++){
                    cin >> a[i];
                }
                printAllPermutation(a, 0, n-1, n);
            }
        }
        int main(){
            test2();
            return 0;
        }

测试：

> 3  
> 1 2 2

结果：

> 122  
> 212  
> 221

正确输出了全排列，并且没有出现重复。 下面考虑从n个元素中挑选m个元素，求这m个元素的排列情况。

#### 2. 求 n 个元素中的 m 个元素的所有排列 ####

也分两种情况考虑，当输入的n个元素不存在和存在重复元素的情况。

（1）输入的n个元素各不相同时

**思路：**和全排列类似的情况，排列重在顺序，先选择谁再选择谁，先选择的第一个元素可能是n个元素中的任意一个，第二个元素可能是剩下n-1个元素中的任意一个…当考虑到选择第 m 个元素时，可能是剩下 n-m 个元素中的任意一个，然后从第 m+1 个元素开始的全排列不用再考虑了，直接输出前面的 m 个元素，这样所有的情况就是从 n 个元素中选择 m 个元素的所有排列情况。 依然要采用递归的方法，只是结束条件变成了当考虑到了第 m+1 个元素。

代码：

void printMPermutation_withRepeat(int a[],int beg, int end,int n, int m){
            if(beg+n-m > end){
                for(int i=0;i<m;i++){
                    cout << a[i];
                }
                cout << endl;
                return;
            }
            for(int i=beg;i<=end;i++){
                swap(a[beg], a[i]);
                printMPermutation_withRepeat(a, beg+1, end, n, m);
                swap(a[beg], a[i]);
            }
        }
        void test3(){
            int n, m;
            while(cin >> n >> m){
                int a[n];
                for(int i=0;i<n;i++){
                    cin >> a[i];
                }
                printMPermutation_withRepeat(a,0,n-1,n,m);
            }
        }
        int main(){
            test3();
            return 0;
        }

测试：

> 3 2  
> 1 2 3

结果：

> 12  
> 13  
> 21  
> 23  
> 32  
> 31

如果输入重复的元素结果中会出现重复，比如：

测试：

> 3 2  
> 1 2 2

结果：

> 12  
> 12  
> 21  
> 22  
> 22  
> 21

（2）当输入的n个元素中存在重复元素时

因为从n个里面挑选m个元素进行排列，本质上还是和全排列一样，所以，直接按照全排列去掉重复的方法，就可以得到不重复的m个元素的排列。

代码：

void printMPermutation(int a[],int beg, int end,int n, int m){
            if(beg+n-m > end){
                for(int i=0;i<m;i++){
                    cout << a[i];
                }
                cout << endl;
                return;
            }
            for(int i=beg;i<=end;i++){
                bool flag = true;
                for(int j=i-1;j>=beg;j--){
                    if(a[j] == a[i]){
                        flag = false;
                    }
                }
                if(flag){
                    swap(a[beg], a[i]);
                    printMPermutation(a, beg+1, end, n, m);
                    swap(a[beg], a[i]);
                }
            }
        }
        void test4(){
            int n, m;
            while(cin >> n >> m){
                int a[n];
                for(int i=0;i<n;i++){
                    cin >> a[i];
                }
                printMPermutation(a,0,n-1,n,m);
            }
        }
        int main(){
            test4();
            return 0;
        }

测试：

> 3 2  
> 1 2 2

结果：

> 12  
> 21  
> 22

### 二、组合问题 ###

考虑从 n 个元素中挑选 m 个元素，考虑一共有多少种组合。 也分两种情况，当输入的 n 个元素中不存在重复元素和存在重复元素的情况。

（1）当 n 个元素中不存在重复的元素时

**思路：**组合问题重在选择与否，而与顺序无关，先考虑是否选择第一个元素，然后再考虑是否选择第二个元素，…，一直进行下去，当统计选择出来的元素达到 m 个时就停止继续往后考虑，直接返回结果。因此需要对选择出来的元素个数进行计数，由于最后要输入选择了哪些元素，因此需要在选择过程中记录选择的元素。

代码：

void printMCombination(int a[], int n, int m, int cur, int &count, bool flag[]){
            if(count == m){
                for(int i=0;i<cur;i++){
                    if(flag[i]){
                        cout << a[i];
                    }
                }
                cout << endl;
                return;
            }
            if(cur >= n){
                return;
            }
            flag[cur] = true;
            count++;
            printMCombination(a, n, m, cur+1, count, flag);
            flag[cur] = false;
            count--;
            printMCombination(a, n, m, cur+1, count, flag);
        }
        void test5(){
            int n, m;
            while(cin >> n >> m){
                int a[n];
                bool flag[n];
                for(int i=0;i<n;i++){
                    cin >> a[i];
                    flag[i] = false;
                }
                int count = 0;
                printMCombination(a, n, m, 0, count, flag);
            }
        }
        int main(){
            test5();
            return 0;
        }

测试：

> 3 2  
> 1 2 3

结果：

> 12  
> 13  
> 23

但是如果输入的n个元素中存在重复的元素时，这个结果中会出现重复的组合，比如：

测试：

> 3 2  
> 1 2 2

结果：

> 12  
> 12  
> 22

（2）当输入的 n 个元素中存在相同的元素时

**思路：**这个没有想到如何在遍历过程中很优雅的去掉重复的选择，能想到的一种方法只是保存下之前已经找到的组合，然后当要向结果中加入新的组合时先判断是否已经存在结果中，如果存在就不再加入，如果不存在就加入组合。但是这种方式也不是很优雅，所以就考虑这个，下面就提供一个先找到有重复的组合情况的结果，然后对结果进行去重。

bool cmp(vector<int> &a, vector<int> &b){
            if(a.size() != b.size())
                return false;
            for(int i=0;i<a.size();i++){
                if(a[i] != b[i]){
                    return false;
                }
            }
            return true;
        }
    
        bool comp(vector<int> &a, vector<int> &b){
            if(a.size()<=b.size()){
                for(int i = 0; i < a.size();i++){
                    if(a[i] != b[i]){
                        return a[i] < b[i];
                    }
                }
                return true;
            } else {
                for(int i=0;i<b.size();i++){
                    if(a[i] != b[i]){
                        return a[i] < b[i];
                    }
                }
                return false;
            }
        }
        //result contains repeated combinations
        void printMCombination(vector<int> &a, int n, int m, int cur, int count, bool flag[], vector<vector<int> > &result){
            if(count == m){
                vector<int> temp;
                for(vector<int>::iterator it = a.begin();it != a.end();it++){
                    if(flag[it-a.begin()])
                    temp.push_back(*it);
                }
                result.push_back(temp);
                return;
            }
            if(cur >= n){
                return;
            }
            flag[cur] = true;
            count++;
            printMCombination(a, n, m, cur+1, count, flag, result);
            flag[cur] = false;
            count--;
            printMCombination(a, n, m, cur+1, count, flag, result);
        }
    
        //not exist repeated combination
        void printMCombination(){
            int n, m;
            while(cin >> n >> m){
                bool flag[n];
                vector<int> a;
                int temp;
                for(int i=0;i<n;i++){
                    cin >> temp;
                    a.push_back(temp);
                    flag[i] = false;
                }
                int count = 0;
                vector<vector<int> > result;
                printMCombination(a, n, m, 0, count, flag, result);
                sort(result.begin(), result.end(),comp);
                vector<vector<int> >::iterator newend = unique(result.begin(),result.end(),cmp);
                for(vector<vector<int> >::iterator it = result.begin();it != newend;it++){
                    for(vector<int>::iterator t = it->begin();t != it->end();t++){
                        cout << *t;
                    }
                    cout << endl;
                }
            }
        }
        int main(){
            printMCombination();
            return 0;
        }

测试：

> 3 2  
> 1 2 2

结果：

> 12  
> 22

无重复的组合了。

如果有人有更好的去掉组合的重复方法，可以在评论区给出见解，谢谢。