Permutation Sequence Solutions in C++

// Source : https://oj.leetcode.com/problems/permutation-sequence/
// Author : Hao Chen
// Date   : 2014-08-22



#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;


/*
"123"
"132"
"213"
"231"
"312"
"321"
*/

void nextPermutation(vector<int>& num); 

/* Extreamly Optimized */
string getPermutation(int n, int k) {
    vector<int> num;
    int total = 1;
    for(int i=1; i<=n; i++){
        num.push_back(i);
        total *= i;
    }

    //invalid k;
    if( total < k ) {
        return "";
    }

    // Construct the k-th permutation with a list of n numbers
    // Idea: group all permutations according to their first number (so n groups, each of
    // (n-1)! numbers), find the group where the k-th permutation belongs, remove the common
    // first number from the list and append it to the resulting string, and iteratively
    // construct the (((k-1)%(n-1)!)+1)-th permutation with the remaining n-1 numbers
    int group = total;
    stringstream ss;
    while (n>0) {
        group = group / n;
        int idx = (k-1) / group;
        ss << num[idx];
        num.erase(num.begin()+idx);
        n--;
        //the next k also can be caculated like this: 
        //    k = (k-1)%group + 1; 
        k -= group * idx;
    }

    return ss.str();
}



/* Optimization by determining the group */
string getPermutation_0(int n, int k) {
    vector<int> num;
    int total = 1;
    for(int i=1; i<=n; i++){
        num.push_back(i);
        total *= i;
    }

    //invalid k;
    if( total < k ) {
        return "";
    }
    int group = total / n;
    int idx = (k-1) / group;
    int nn = num[idx];
    num.erase(num.begin()+idx);
    num.insert(num.begin(), nn);

    int offset = (k-1) % group;
    for(int i=0; i<offset; i++) {
        nextPermutation(num);
    }

    //string result;
    stringstream ss;
    for(int i=0; i<n; i++){
        ss << num[i];
    }

    return ss.str();
}

/* Time Limit Exceeded */
string getPermutation_1(int n, int k) {
    vector<int> num;
    for(int i=1; i<=n; i++){
        num.push_back(i);
    }

    for(int i=1; i<k; i++) {
        nextPermutation(num);
    }

    //string result;
    stringstream ss;
    for(int i=0; i<n; i++){
        ss << num[i];
    }

    return ss.str();
}



void nextPermutation(vector<int>& num) {
    if (num.size()<=1) return;
    for (int i=num.size()-1; i>0; i-- ) {
        if (num[i-1] < num[i]) {
            int j = num.size() - 1;
            while( num[i-1] > num[j] ) {
                j--;
            }
            int temp = num[i-1];
            num[i-1] = num[j];
            num[j] = temp;

            reverse(num.begin()+i, num.end());
            return;
        }
    }

    reverse( num.begin(), num.end() );
}


int main(int argc, char**argv)
{
    int n=3, k=6;
    if ( argc > 2 ) {
        n = atoi(argv[1]);
        k = atoi(argv[2]);
    }
    cout << "n = " << n << ", k = " << k << " : " << getPermutation(n, k) << endl;

    return 0;
}

#include <string>
using std::string;
#include <numeric>

class Solution {
public:
    string getPermutation(int n, int k) {
        int table[10] = {1};
        for (int i=1; i<=9; ++i)
            table[i] = i*table[i-1];
        
        string dict(n, ' '), ret(dict);
        std::iota(dict.begin(), dict.end(), '1');
        
        for (int i=0; n>0; --n) {
            int pos = (k-1)/table[n-1];
            ret[i++] = dict[pos];
            dict.erase(dict.begin()+pos);
            k = k - pos * table[n-1];
        }
        return ret;
    }
    
};