Permutation Sequence

One straightforward solution would be to call the next_permutation and count the calling times, but it is not necessary to do the actual permutation, we just need to find out which digit in which position.

Here is the idea. For each k, divide the number of previous permutations into some factorials, for each factorial, count how many and save this info into an index array. Based on this array, we can choose which digit at each position. e.g, for n=4, k=20, it has 19 permutations before, 19 = 33! + 02! + 1*1! + 0, so the index[] would be 0,1,0,3 (reversing order), which can be interpreted as the order of digit in an ordered array, e.g, 3 means arr[3] in [1,2,3,4] which is 4.

public:
string getPermutation(int n, int k) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    assert(1<=k && k<=fact(n));

    string s;
    int i;        
    vector<int> index(n,0);

    int kk = k - 1;
    for (i=n-1; i>=0; i--) {
        while (kk >= fact(i)) { //index[i] * i! 
            index[i]++;
            kk -= fact(i);
        }
    }

    vector<int> arr;
    for (i=0; i<n; i++) arr.push_back(i+1);
    for (i=n-1; i>=0; i--) {
        s = s + (char)(arr[index[i]] + '0');
        arr.erase(arr.begin() + index[i]);
    }
    return s;
}
private:
int fact(int n)
{
    int f = 1;
    for (int i=n; i>0; i--)
        f = f * i;
    return f;
}

class Solution {
public:
    string getPermutation(int n, int k) {
        string      result;
        vector<int> num(n);
        int         i, d(1), q;
        for(i=1;i<=n;++i){
            num[i-1]  = i;
            d        *= i;  //d=n!
        }
        for(i=n;i>=1;--i){
            d       = d/i;
            q       = (k-1)/d;
            k       = k-q*d;
            result.push_back('0'+num[q]);
            num.erase(num.begin()+q);
        }
        return result;
    }
};

string getPermutation(int n, int k) {
    string str;
    vector<int> factorial(n + 1, 1);
    for (int i = 1; i <= n; ++i) {
        str += i + '0';
        factorial[i] = factorial[i-1] * i;
    }
    string perm;
    --k;    // convert to 0-based index
    for (int i = n - 1; i >= 0; --i) {
        int quotient = k / factorial[i];
        perm += str[quotient];
        str.erase(quotient, 1);
        k %= factorial[i];
    }
    return perm;
}

public static int fact(int n) {
    if(n == 0 || n ==1)
        return 1;
    return n * fact(n-1);
}

public static String getPermutation(int n,int k) {

    String res = "";        
    int fact = fact(n);
    int no = n;

    boolean[] used = new boolean[n+1];
    for(int i=0;i<=n;i++) {
        used[i] = false;
    }

    while(res.length() < no) {
        fact /= n;
        int j=0;
        while(k > 0) {
            if(j!=0 && !used[j]) 
                k -= fact;  
            j++;                
        }           
        used[j-1] = true;
        k += fact;
        res += j-1;
        n--;            
    }       
    return res;     
}

    class Solution {
public:
    string getPermutation(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        string ret;
        if(n==0 || k==0)
            return ret;
        if(k>fac(n))
            return ret;
        for(int i=1; i<=n; i++)
            ret+='0'+i;
        k--; n--;
        int pos=0, posdiff=0, subsize=0;
        string tmp;
        while(k>0){
            subsize=fac(n);
            posdiff=k/subsize; k=k%subsize;
            if(posdiff>0){
                tmp=ret[pos+posdiff];
                ret.erase(pos+posdiff, 1);
                ret.insert(pos, tmp);
            }
            pos++;
            n--;
        }
        return ret;
    }
    int fac(int n){
        if(n==0 || n==1)
            return 1;
        int ret=1;
        for(int i=2; i<=n; i++)
            ret*=i;
        return ret;
    }

};