trjhtr

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.

• 
  

  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