kthPermutation.cpp

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <map>

using namespace std;


int fact(int n) {
    int result = 1;
    while (n != 0) {
        result *= n;
        n--;
    }
    return result;
}

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;
}

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;
}

ostream & operator << (ostream & os, const vector<int> &vec)
{
    cout << "[";
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i];
        if (i != vec.size() - 1)
            cout << ",";
    }
    cout << "]";
    return os;
}

int main(int argc, char *argv[])
{
    const int size = 4;
    int a[size] = {1,2,2,3};
    vector<int> vec(a, a+size);

    int n_perms = fact(size);
    for (int i = 0; i < n_perms; i++) {
        vector<int> perm = kth_permutation(vec, i);
        cout << perm << endl;
        cout << "rank: " << permutation_rank(perm) << endl;
    }
    
    
    return 0;
}