# 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 <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.

• Any particular C++ standard you are using for this? C++11/14/17? – Arnav Borborah Feb 27 '18 at 1:23
• Doesn't matter. For sake of reference, C++17. – FatalSleep Feb 27 '18 at 2:11

• 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

• std::iota() isn't a direct replacement there - it's a shame there's no std::iota_n that could take a back-insert iterator. – Toby Speight Feb 27 '18 at 8:44
• Thank you for the answer I've revised my code to include comments. My apologies it's not the best code/commented. I mocked it up really quick. – FatalSleep Feb 27 '18 at 17:15
• @vnp unfortunately std:iota() doesn't work here if s is a length of 0. Unless I defined s as vector<uint64_t> s(N); which might save some performance, if any. – FatalSleep Feb 27 '18 at 17:25
• @vnp I'll try out your changes here and get back to you. I don't care how it produces the permutations, just that it produces them faster and without duplicates and covers the N! number of permutations requirements. – FatalSleep Feb 27 '18 at 17:30