Permutation的各种形态

2017-06-18

概述

Permutaion是一个很经典的问题，可以有多种变形，很多问题也可以抽象为permutation，然后进行求解。

本文主要内容:

经典Permutation
next-Permutation
\(kth\) Permutation

解决思想

经典Permutation

经典Permutation：例如1,2,3三个数，输出他们的全排列：
1,2,3
1,3,2
2,1,3
2,3,1
3,1,2
3,2,1

交换（递归）

思路很简单，对于第一个数，可以和其后面的每一个数交换。依次递归，第二个数也可以和其后面的每个数交换，以此类推。


void Permutation(int a[3], int start){
    if (start == 3){
        cout << a[0] << a[1] << a[2] << endl;
        return;
    }
    for (int i = start; i < 3; i++){
        swap(a[start], a[i]);
        Permutation(a, start+1);
        //一定记得将状态复原（回溯）
        swap(a[start], a[i]);
    }
}

交换（非递归）

这个思路也很好理解，主要是利用逆序对。初始化的数组是一个升序排列。

我们从后往前，找到第一个非逆序对，nums[i]表示较小的那个，nums[i+1]则表示较大的。
再从后往前找到第一个大于nums[i]数，将其与nums[i]交换。
对于i以后的数，将其做一个反转（本来是降序的，做完变为升序）。

vector<int> nums;
//nums中的数初始化为升序排列
int n = nums.size();
while(1){
    for (int i = n - 2; i >= 0 && nums[i] > nums[i+1]; i--);
    if(i < 0) break;
    for (int j = n - 1; j >= 0 && nums[j] < nums[i] ; j--);
    swap(nums[i], nums[j]);
    //将从i+1开始的所有数reverse，使其变为升序排列
    reverse(nums, i+1, n-1);
    输出nums中的所有数;
}

next-Permutation

给出全排列中的一个结果，输出的它的写一个排列。
这个我们可以直接利用上文中的 交换（非递归） 的思想：
对于给出的排列，我们从后往前找到第一个非逆序对，然后步骤同 交换（非递归） 的2、3步。

注意：

//说明已经是最后一种
if(i < 0){
    输出最开始初始化的排列;
}

\(kth\) Permutation

对于全排列，给出它的第k个排列，例如：对于123,它的第3个排列就是：
213

方法一：

将Permutation的结果都存起来，然后直接取第k个结果。
或者利用next-permutation的方法，循环k次，就得到第k个排列。

方法二：

对于1~n的全排列，利用数学方法，也可以轻易求解。用一个visit数组做辅助。一位一位地获得数字，利用k / (n-1)!，以及k % (n - 1)!,然后n = n - 1, 一位一位地选出数字，将visit数组标记，即可得到结果。

string getPermutation(int n, int k){
    string res = "";
    vector<bool> vis(n);
    char c = '0';
    int num = 0;
    int i, j;
    int N = n;
    int cnt = 0;
    for (i = 0; i < n; i++) vis[i] = false;
    while(k != 0){
        //自定义的求阶层函数
        num = stratum(--N);
        cnt = k / num;
        if (k % num != 0) cnt++;
        
            j = 0;
            while(cnt){
                if (vis[j] == false){
                    cnt--;
                }
                j++;
            }
            vis[j - 1] = true;
            res += c + j;
        k = k % num;
    }
    //从大到小排进剩余的位置
    for (i = n - 1;i >=0; i--){
        if (vis[i] == false){
           res += c + i + 1;
           vis[i] = true;
        }
    }
    return res;
}