求序列的全排列（C++ ）

求全排列并不难，但是在一些问题求解过程中经常需要用到，例如典型的24点游戏问题。下面直接上代码了，参考注释不难看懂。

#include<iostream>
#include<array>
#include<algorithm>
using namespace std;

void display(array<int,4> arr)
{
    for(auto value:arr){
        cout<<value<<" ";
    }
    cout<<endl;
}

/*
对于包含相同元素的序列来说，只要一个序列中的元素顺序不同，就是一种排列。
next_permutation() 会生成一个序列的重排列，它是所有可能的字典序中的下
一个排列，默认使用 < 运算符来做这些事情。它的参数为定义序列的迭代器和一个
返回布尔值的函数，这个函数在下一个排列大于上一个排列时返回 true，如果上一
个排列是序列中最大的，它返回 false，所以会生成字典序最小的排列。
所以想通过next_permutation()来获得一个序列的全排列，就要保证初始状态下，
序列是字典序中最小的，这样通过next_permutation()循环才能生成完整的排列
*/
void getPermutation1(array<int,4> arr)
{
    sort(arr.begin(),arr.end());  //如果将此行注释，最终结果会不完整
    do{
        display(arr);
    }while(next_permutation(arr.begin(),arr.end()));
}

//回溯法求排列组合
int getPermutation2(array<int,4> arr,int index)
{
    //触发结束条件
    if(index==4){
        display(arr);
        return 0;
    }
    for(int i=index;i<4;++i){
        //做选择
        int temp=arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
        getPermutation2(arr,index+1); //进入下一层决策树
        //取消选择
        temp=arr[index];
        arr[index] = arr[i];
        arr[i] = temp;
    }
    return 0;
}

int main(int argc,char **argv)
{
    array<int,4> arr={3,2,1,0};
    cout<<"----基于字典序的排列组合----"<<endl;
    getPermutation1(arr);
    cout<<"----回溯算法求得的排列组合----"<<endl;
    getPermutation2(arr,0);
    return 0;
}

运行结果截图如下：

基于字典序的排列组合	回溯算法求排列组合

next_permutation()算法原理可以参考我上一篇字典序算法笔记。

以上只是简单的打印求得的排列，如果想要保存全排列结果，可以借助二维数组。下面还是基于回溯算法的求解全排列过程，只不过将求得的全排列放在二维数组里了。

/*题目描述： 
给定一个不包含重复的数组，返回所有可能的排列。
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//回溯算法   
void backtrack(vector<int>& nums, vector<vector<int>>& result, vector<int>& path){
    //触发结束条件
    if(path.size() == nums.size()){
        vector<int> temp = path;
        result.push_back(temp);
    }else{
        for(int i = 0; i< nums.size(); i++) {
            //排除不合法的选择
            if(find(path.begin(), path.end(),nums[i]) != path.end()) continue;
            path.push_back(nums[i]); //做选择
            backtrack(nums, result, path); //进入下一层决策树
            path.pop_back(); //取消选择
        }
    }
}

vector<vector<int> > permute(vector<int>& nums) {
    vector<vector<int> > result;
    vector<int> path; //记录临时路劲
    backtrack(nums, result, path);
    return result;
}

void display(vector<vector<int> > v)
{
    for(auto arr:v){
        for(auto value:arr){
            cout<<value<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

int main(int argc,char **argv)
{
    int a[]={3,2,1,0};
    vector<int> v(a,a+4);
    vector<vector<int> > result;
    result=permute(v);
    display(result);
    return 0;
}