排列问题

于是就有了一个很简单的递归关系:

kth_perm(perm, k) = perm[k/(n-1)!]  +  kth_perm(perm[0..i-1] + perm[i..n-1], k % (n-1)!)

根据这个关系可以写出kth_permutation的代码:

    vector<int> kth_permutation(const vector<int> &vec, int k)    {        if (k == 0)            return vec;        int n = vec.size();        k %= fact(n);        int t = fact(n-1);        int i = k / t;        int kk = k % t;        vector<int> result;        result.push_back(vec[i]);        vector<int> left;        copy(vec.begin(), vec.begin()+i, back_inserter(left));        copy(vec.begin()+i+1, vec.end(), back_inserter(left));        left = kth_permutation(left, kk);        copy(left.begin(), left.end(), back_inserter(result));        return result;    }

Permutation Rank

给定一个排列”231”, 它是”123”的排列中第几大的?

由于2是第1大的, 因此有 2! * 1 个首位比 2 小的.

由于3是剩下的数中第1大的, 因此有 1! * 1 个第二位比3小的.

因此比”231”小的 有 2! * 1 + 1 ! * 1 = 3个, 因此”231”是第3大的. (均从0开始)

一个比较naive的实现：

    int permutation_rank(vector<int> &vec)    {        vector<int> vec2(vec.begin(), vec.end());        sort(vec2.begin(), vec2.end());        map<int, int> ranks;        for (int i = 0; i < vec2.size(); i++) {            ranks[vec2[i]] = i;        }        int rank = 0;        int n = vec.size();        for (int i = 0; i < vec.size(); i++) {            rank += fact(n-1) * ranks[vec[i]];            for (map<int, int>::iterator it = ranks.begin(); it != ranks.end(); ++it) {                if (it->first > vec[i])                    it->second--;            }            n--;        }        return rank;    }

Next permutation

已知一个排列”146532”, 如何求出比它大的下一个排列? 这个问题被称为next_permutation.

一个简单的方法是, 使用前面的结论, 首先求出rank, 然后求第rank+1的排列. next_permutation(vec): k = rank(vec) return kth_permutation(vec, k+1)

不过也有一个更加subtle, 效率也更高的方法:

首先找出最大的i ,使得 a[i] < a[i+1], 例如 1 4 6 5 3 2 i此时, a是所有以a[0..i]开头的排列中最大的. 也就是说,1 4 6 5 3 2是所有 1 4 开头排列中最大的. (如果这一步找不到, 说明原序列倒序排列, 已经是最大的一个排列了.)

现在我们要使a变大, 但是变大的幅度要尽可能小, 因此我们要找到一个刚好比a[i]大的数, 也就是比a[i]大的数中最小的一个.

因此,我们找出最大的j, 使得 a[i] < a[j]: 1 4 6 5 3 2 i j

a[j]就是比a[i]大的数中最小的一个. 我们把它和a[i]交换: 1 5 6 4 3 2 i j

此时, a是 a[0..i]开头的数中最大的一个, 这不满足我们的要求, 我们希望它是最小的一个. 因此, 我们将a[i+1..n-1]倒序: 1 5 2 3 4 6

即为所求. c++实现:

    void reverse(vector<int> &num, int i) {        for(int j = num.size() - 1; j > i; j--) {            swap(num[i], num[j]);            i++;        }    }        void nextPermutation(vector<int> &num) {        if (num.size() <= 1) {            return;        }                // find max i where num[i] < num[i+1]        int i;        for (i = num.size()-2; i >= 0 && num[i] >= num[i+1]; i--);        if (num[i] >= num[i+1]) {            reverse(num, 0);            return;        }        // find max j where num[i] < num[j]        int j;        for (j = num.size()-1; num[i] >= num[j]; j--);        swap(num[i], num[j]);