Calculate permutation from Factorial representation of the K-th iteration of the N-th permutation

Question

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 <iostream>
#include <vector>
#include <cmath>
using namespace std;

///<summary>Calculates the permutation of K in range of 0 to N!. (MAX of N = 20--2^61).</summary>
vector<size_t> factorial_permutation(size_t N, uint64_t K) {
    vector<size_t> 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 > 1; I--)
        FactN *= I;
    for (uint64_t I = 1; I <= 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<size_t> c = factorial_permutation(N, K);
    vector<size_t> s; //The factorial permutation sequence
    vector<size_t> e; //The permutation built from the factorial sequence

    //Builds the basic order sequence 0 to N-1 before permutation.
    for(int i = 0; i < 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 < N; i++) {
        e.push_back(s[c[i]]);
        s.erase(s.begin() + c[i]);
    }

    // Outputs the final permutation.
    for (int i = 0; i < N; i++)
        cout << 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.

Answer 1

• The loop

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

  is idiomatically expressed as std::iota(s.begin(), s.end(), 0) (you'd need to #include <numeric>).

• A no naked loops principle demands giving a name to the

      for (int i = 0; i < 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 < 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 > 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