Calculate permutation from Factorial representation of the K-th iteration of the N-th permutation As a follow of a post I made on the Mathematics Stack Exchange I wrote out a simple program that computes the K-th permutation from 0 to N-1 where the number of permutations is N!. What I was wondering is could I get some pointers on how to improve and re-write the permutation function to be more efficient--e.g. possibly getting rid of the vector and the for-loop to calculate the factorial.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;cmath&gt;
using namespace std;

///&lt;summary&gt;Calculates the permutation of K in range of 0 to N!. (MAX of N = 20--2^61).&lt;/summary&gt;
vector&lt;size_t&gt; factorial_permutation(size_t N, uint64_t K) {
    vector&lt;size_t&gt; Perm;

    uint64_t FactN = N,  //Factorial of N
        RmdrK = K, //Remainder of K/(N-1)!
        IterN = N, //Downward iterator for N
        PostK; //The factorial position of K for each sub permutation.

    for(uint64_t I = N-1; I &gt; 1; I--)
        FactN *= I;
    for (uint64_t I = 1; I &lt;= N; I++) {
        FactN /= IterN--;
        PostK = RmdrK / FactN;
        RmdrK = RmdrK - (PostK * FactN);
        Perm.push_back(PostK);
    }

    return Perm;
}

int main() {
    size_t N = 0;
    uint64_t K = 0;
    vector&lt;size_t&gt; c = factorial_permutation(N, K);
    vector&lt;size_t&gt; s; //The factorial permutation sequence
    vector&lt;size_t&gt; e; //The permutation built from the factorial sequence

    //Builds the basic order sequence 0 to N-1 before permutation.
    for(int i = 0; i &lt; N; i++)
        s.push_back(i);

    //Pushes the final result converted from factorial permutation to real permutation. For each entry of sequence s[c[i]] is an index into e[i] to build the permutation.
    for (int i = 0; i &lt; N; i++) {
        e.push_back(s[c[i]]);
        s.erase(s.begin() + c[i]);
    }

    // Outputs the final permutation.
    for (int i = 0; i &lt; N; i++)
        cout &lt;&lt; e[i];

    cin.get();
};


The function factorial_permutation calculates the factorial representation of K--the K-th iteration--in a sequence from 0 to (N-1)! possible permutations. The main() function does simple conversion from the factorial representation to building the actual sequence. I would like to combine the two and see if I can negate the vectors all together for the sake of performance.

I'm also aware that I can remove the vector in factorial_permutation by using a basic array, but I can't seem to negate the one in the main() function.
The loop

for(int i = 0; i &lt; N; i++)
    s.push_back(i);


is idiomatically expressed as std::iota(s.begin(), s.end(), 0) (you'd need to #include &lt;numeric&gt;).
A no naked loops principle demands giving a name to the

    for (int i = 0; i &lt; N; i++) {
        e.push_back(s[c[i]]);
        s.erase(s.begin() + c[i]);
    }


loop. It surely represents an important algorithm. What exactly does it do?

In any case, the s and e vectors shall not be exposed to the client.
Computing factorials restricts the utility of the code to N &lt; 21 (21! = 0x2_c507_7d36_b8c4_0000 doesn't fit in 64 bits). Unfortunately you cannot even express K within uint64_t limits for larger N. Consider BigInteger.
It is possible to avoid factorials (as well as ancillary vectors) by working other way around. Consider a pseudocode:

    while N &gt; 0:
        index = K % N
        swap a[N-1] with a[index]
        K /= N
        N -= 1


While correct, it doesn't produce the same K'th permutation as your code does. May I suggest changing it to produce the correct sequence as an exercise?


PS: a mandatory warning on using namespace std