数组元素的全排列算法，重复全排列算法，子集求解算法，任意排列算法

我不是女神ヾ 2022-05-14 06:29 256阅读 0赞

输出字符数组的全排列，这个问题利用递归的方式比较简单。数组的重复全排列与全排列的区别主要相当于（有放回还是没有放回）。

输出字符数组的所有排列，包括全排列，单个元素，多个元素的排列，这就稍微有点复杂了，比较好的思路就是先对数组进行子集的提取，然后对每一个子集进行全排列。子集的获取有两种途径，

第一个循环的方法，主要就是利用与数组等大小的二进制数（数学中非空子集的个数=(2^size)-1)，因此二进制数中为1的位置表示子集中有该位置的元素。

第二个递归的方法，主要是利用递归的思想，输出与数组等大小所有可能的（0，1）序列，后续思路与上面循环的方法一样。

#include <iostream>
    #include <vector>
    #include <deque>
    
    using namespace std;
    
    //重复全排列
    void mul_quanpailie(vector<char>* s, int position, vector<char>* result){
        //递归终止条件，result中已经保存了所有的可能性值，和s等大小
        if(position == int(s->size())){
            for(auto i = result->begin();i!=result->end();i++){
                cout << *i << " ";
            }
            cout << endl;
        }
        else{
            //result的每一个位置，有可能是s中任意一个值
            for(auto it = s->begin(); it != s->end(); it++){
    //            (*result)[position] = *it;
                result->push_back(*it);
                mul_quanpailie(s,position+1,result);
                result->pop_back();
            }
        }
    }
    
    //全排列函数
    void quanpailie(vector<char>* s, int position){
        //递归终止判定
        if(position == int(s->size())){
            for(auto it = s->begin();it!=s->end();it++){
                cout << *it << " ";
            }
            cout << endl;
        }
        else{
            //全排列函数
            for(auto i = position;i<int(s->size());i++){
                char temp = (*s)[i];
                (*s)[i] = (*s)[position];
                (*s)[position] = temp;
                quanpailie(s,position+1);
                temp = (*s)[i];
                (*s)[i] = (*s)[position];
                (*s)[position] = temp;
            }
        }
    }
    
    //循环找子集,并全排列
    void print_alls(vector<char>* s){
        int size = s->size();
        int t = 1<<size;
        //按照i的二进制进行分组，i的二进制中为1的地方，表示子集中有这个元素
        for (int i = 1; i <= t - 1; i++)
        {
            vector<char>* temp = new vector<char>;
            for (int j = 0; j <= size; j++)
            {
                //找到第j个位置，对应该位置i二进制中为1
                if ((1 << j)&i){
    //                cout << (*s)[j] << " ";
                    temp->push_back((*s)[j]);
                }
            }
            //子集元素保存在temp中
            if(temp!=NULL){
                quanpailie(temp,0);
            }
            delete temp;
            temp = NULL;
        }
    }
    
    //递归找子集，并全排列
    void print_alls_DG(vector<char>* s, int position, vector<int>* cur){
        if(position == int(s->size())){
            int i = 0;
            vector<char>* temp = new vector<char>;
            while(i<position){
                if((*cur)[i] == 1){
                    temp->push_back((*s)[i]);
                }
                i++;
            }
            if(temp->size()>0){
                quanpailie(temp,0);
            }
            delete temp;
            temp = NULL;
        }
        else{
            //这一步相当于将（0,1）排列在cur中，和之前扔骰子一样
            for(int i = 0; i < 2; i++){
                (*cur)[position] = i;
                print_alls_DG(s,position+1,cur);
            }
        }
    }
    
    
    int main(){
        vector<char>* s = new vector<char>;
        *s = {'a','b','c'};
        cout << "xunhuan+quanpailie" << endl;
        print_alls(s);
        int position = 0;
        vector<int>* result = new vector<int>;
        result->resize(s->size());
        cout << "digui+quanpailie" << endl;
        print_alls_DG(s,position,result);
        vector<char>* result1 = new vector<char>;
        cout << "quanpailie" << endl;
        quanpailie(s,0);
        cout << "chongfuquanpailie" << endl;
        mul_quanpailie(s,0,result1);
        return 0;
    }