全排列算法代码实现，以及用全排列解决八皇后问题（C++代码实现）

快来打我* 2022-05-16 12:53 144阅读 0赞

全排列算法（字符串的全排列和数组容器的全排列）算法：

# include <iostream>
    # include <vector>
    using namespace std;
    
    void begin_arrange(string& s, unsigned int begin);
    void arrange_string(string& s){
        if(s.size()<1){
            return;
        }
        //注意数据类型
        unsigned int i = 0;
        begin_arrange(s,i);
    }
    
    void begin_arrange(string &s, unsigned int begin){
        if(begin==s.size()-1){
            cout << s << endl;
        }
        else{
            for(unsigned int i = begin;i<s.size();i++){
                //交换元素
                char temp = s[begin];
                s[begin] = s[i];
                s[i] = temp;
                //从下一个元素开始
                begin_arrange(s,begin+1);
                //复位元素
                temp = s[begin];
                s[begin] = s[i];
                s[i] = temp;
            }
        }
    }
    
    void begin_vector_arrange(vector<int>* vec, unsigned int begin){
        //终止条件，全排列到最后一个时
        if(begin == vec->size()-1){
            for(auto i = vec->begin();i!=vec->end();i++){
                cout << *i << "->";
            }
            cout << "end" << endl;
        }
        else{
            for(unsigned int i = begin;i<vec->size();i++){
                //begin位置的元素和容器中元素互换
                int temp = (*vec)[begin];
                (*vec)[begin] = (*vec)[i];
                (*vec)[i] = temp;
                //递归，从下一个元素开始
                begin_vector_arrange(vec, begin+1);
                //交换元素复位
                temp = (*vec)[begin];
                (*vec)[begin] = (*vec)[i];
                (*vec)[i] = temp;
            }
    
        }
    }
    
    void arrange_vector(vector<int>* vec){
        if(vec->size()<1){
            return;
        }
        else{
            begin_vector_arrange(vec, 0);
        }
    }
    
    
    int main(){
        string s = "abc";
        arrange_string(s);
        vector<int>* a = new vector<int>;
        *a = {1,2,3,4};
        arrange_vector(a);
        return 0;
    }

全排列方法解决八皇后问题：思路（赋值queens数组，8维数组，每维代表一列，然后每一维赋值一个元素（从0到7），0~7代表该列中第几行，因此这样可以保证矩阵中元素不同列，不同行，接下来求取全排列，然后从其中排除掉那些处于对角线的情况，即abs(queens\[i\]-queens\[j\]) == abs(i-j)时，矩阵有对角线上元素。）具体代码如下所示：

# include <iostream>
    # include <vector>
    
    using namespace std;
    
    //判断是否有交叉，因为主函数的全排列考虑了没有元素在同一行或者同一列
    bool judge_cross(vector<int>* queens){
        for(int i = 0; i<int(queens->size()-1); i++){
            for(int j = i+1; j<int(queens->size());j++){
                //在对角线的判断依据是，数组值的差绝对值等于下标差绝对值
                if((*queens)[i] - (*queens)[j] == i -j || (*queens)[i] - (*queens)[j] == j - i){
                    return true;
                }
            }
        }
        return false;
    }
    
    //其实就是一个全排列模型
    void countQueens(vector<int>* queens, unsigned int key, int& count){
        if(key == queens->size() - 1){
            //不位于对角线
            if(!judge_cross(queens)){
                count = count + 1;
                for(auto i = queens->begin();i!=queens->end();i++){
                    cout << *i << "->";
                }
                cout << "end" << endl;
            }
        }
        else{
            unsigned int size = queens->size();
            for(unsigned int i=key;i<size;i++){
                //所有其他的元素跟第一个元素交换
                int temp = (*queens)[i];
                (*queens)[i] = (*queens)[key];
                (*queens)[key] = temp;
                //递归，除去第一个元素
                countQueens(queens, key+1, count);
                //复位交换元素
                temp = (*queens)[i];
                (*queens)[i] = (*queens)[key];
                (*queens)[key] = temp;
            }
        }
    }
    
    //int main(){
    //    vector<int>* queens = new vector<int>;
    //    *queens = {0,1,2,3,4,5,6,7};
    //    unsigned int key = 0;
    //    int count = 0;
    //    countQueens(queens, key, count);
    //    cout << count << endl;
    //    return 0;
    //}