本文解说4道关于permutation的题目:

1. Permutation：输出permutation——基础递归 
2. Permutation Sequence: 输出字典序排列的第k个permutation——推理
3. Next Permutation：给定一个permutation中的序列，求字典序它的下一个permutation是什么——逻辑推理
4. Permutation II：和第一题有细微的区别: 对于一个可能有反复元素的数组输出全部permutation——有条件dfs

1. Permutation：输出permutation

——基础递归

 class Solution{

     private:

         vector<vector<int> > L;

         vector<int> Nums;

         int l;

         vector<bool> visited;

     public:

         void perm(vector<int>& list){

             if(list.size()==l){

                 L.push_back(list);

                 return;

             }

             for(int i=0; i<l; i++){

                 if(!visited[i]){

                     list.push_back(Nums[i]);

                     visited[i] = true;

                     perm(list);

                     list.pop_back();

                     visited[i] = false;

                 }

             }

         }

         vector<vector<int> > permute(vector<int> &num){

             int i;

             Nums = num;

             l = Nums.size();

             for(i=0;i<l;i++)

                 visited.push_back(false);

             vector<int>list;

             perm(list);

             //for(i=0;i<L.size();i++){

             //    for(int j = 0;j<l;j++)

             //        cout<<L[i][j];

             //    cout<<endl;

             //}

             return L;

         }

 };

2. Permutation Sequence: 输出字典序排列的第k个permutation

——逻辑推理

酱想。n位的permutation有n！个。那么第k个permutation假设满足n!<k<(n+1)!就一定有，

a = k/n!

b = k%n!

取集合里的第a位做下一位。下一次分析剩下的字符组成的第b个permutation

------------------------

e.g. 求[1,2,3,4]组合的第10个

①求[1,2,3,4]组合的第10个

10/3! = 1…4 --->找到[1,2,3,4]中第(1+1)个数(2)做下一位，留下[1,3,4]

②求[1,3, 4]组合的第10-3! * 1 = 4个

4/2! = 2…0 --->找到[1,3,4]中第2个数(3)做下一位, 留下[1,4]

③余零。说明是permutation里的最后一个 -> 剩下的逆序输出

--->2341

class Solution {

public:

    string getPermutation(int n, int k) {

        int i,j,sum = 1;

        //sum = (n-1)!

        for (i=2; i<n; i++) {

            sum *= i;

        }

        bool visited[n+2];

        memset(visited, false, sizeof(visited));

        string str;

        for(i=1;i<n;i++){

            int nextidx = k/sum;

            k = k%sum;

            if(k==0)

                nextidx -- ;

            sum/=(n-i);

            int cnt = 0;

            for (j=0; j<n; j++) {

                if (!visited[j]) {

                    if (cnt == nextidx){

                        visited[j] = true;

                        str += '0' +j+1;

                        break;

                    }

                    cnt ++;

                }

            }

        }

        for(j=n-1;j>=0;j--){

            if (!visited[j]) {

                str += '0' + j+1;

            }

        }

        return str;

    }

};

3. Next Permutation

给定一个permutation中的序列，求字典序它的下一个permutation是什么。

——逻辑推理

能够发现，下一个permutation能够这么得来：

①当前permutation从后往前找到一直上升的子序列，假如一直上升到index_i

②找到index为i到end中最小的。比num[i-1]大的数字,记index为j。交换num[i-1],num[j]

③对num[i]~num[end]从小到大排序

PS：要注意有反复元素的情况e.g {1,5,1};

code：

class Solution {

public:

    void nextPermutation(vector<int> &num) {

        size_t n = num.size();

        int i = (int)n-1;

        int j=0;//find the position that stops increasing from tail

        while(num[i]<=num[i-1] && i>0)

            i--;

        sort(num.begin()+i, num.end());

        //find the digit that substitute(swap with) i

        for(j=i;j<n;j++){

            if (num[j]>num[i-1]) {

                break;

            }

        }

        if(i>0 && j<n)

            swap(num[i-1], num[j]);

    }

};

4. Permutation II

和第一题有细微的区别: 对于一个可能有反复元素的数组输出全部permutation。

——有条件dfs

想一下递归条件：

肯定还是递归，递归条件应该是假设当前list中已经出现过这几个元素排列。就不要再加进去。

所以在第一题基础上仅仅加两点：

1）对数组里全部元素排序

2）对于上一次加到过list的同样元素（必定是在排序后数组中与上一个相邻元素同样的）不要再加

class Solution{

private:

    vector<vector<int> > L;

    vector<int> Nums;

    int l;

    vector<bool> visited;

public:

    void perm(vector<int>& list){

        if(list.size()==l){

            L.push_back(list);

            return;

        }

        for(int i=0; i<l; i++){

            if(!visited[i]){

                list.push_back(Nums[i]);

                visited[i] = true;

                perm(list);

                list.pop_back();

                visited[i] = false;

                while (i<l && Nums[i+1]==Nums[i]) {

                    i++;

                }

            }

        }

    }

    vector<vector<int> > permuteUnique(vector<int> &num){

        int i;

        Nums = num;

        l = Nums.size();

        sort(Nums.begin(),Nums.end());

        for(i=0;i<l;i++)

            visited.push_back(false);

        vector<int>list;

        perm(list);

        return L;

    }

};