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.