Fast forwarding the std::next_permutation algorithm

I started my computer with a project that looks more and more like Sisyfos work.

It is trying to solve a puzzle by running through a set of permutations, and it is using std::next_permutation.

However, a day into the computation I realized that the algorithm could be further improved. Should I stop the calculation and restart it? Or let it continue, with the ineffective algorithm?

Looking at the internet I found an in depth explanation of std::next_permutation Implementation Explanation. std::next_permutation will from a starting point increase the permutation in an lexical fashion until it rolls over and returns false:

std::vector<int> skip_next_list = { 1,2,3,4, 5, 6, 7, 8, 9, 10, 11};
do {
//some work here
} while (std::next_permutation(skip_next_list.begin(), skip_next_list.end()));


My search had reached 309000000 when I aborted the job, so I needed to fast forward to that point. I realized that for 6 iterations (3!) it would update the last three entries of skip_next_list, for 24 (4!) the last four and so on.

So this is the skip_next_permutation function, fast forwarding to a number far into the sequence of std::next_permutation.

template<typename It> void skip_next_permutation(uint64_t skip_num, It begin, It end)
{
 if (skip_num <= 0) return; // does not have to be an error

 //build a lut of factorials, this could be a static
 std::vector<uint64_t> factorials;
 factorials.push_back(1); ///  0! == 1
 long idx = 1;
 long input_length = end - begin;
 do {
  factorials.push_back(factorials[idx-1] * idx);
 } while (factorials[++idx - 1] <= skip_num); //

 // now start to loop, find the factorial that is one smaller than the number we want to skip forward

 long my_inc = factorials.size() - 2; // always 2 lower than factorials.size()

 do
 {
  int quotient = skip_num / factorials[my_inc];
  skip_num = skip_num%factorials[my_inc]; //the remaider are the remaining skip_num

  if (skip_num == 0 && quotient == 0) goto end_loop;
  std::swap(begin[input_length - my_inc - 1], begin[input_length - my_inc + quotient - 1]);
  std::sort(begin + input_length - my_inc, end); //avoid with clever management?
  my_inc--;
 } while (my_inc >= 1);
end_loop:
 return;
}

The following table shows the factorials std::next_permutation algorithm exhausted, the number used for skip_next_permutation and the time std::next_permutation used.

Factorial	Number	Time / ms
9!	362 879	0.9
12!	39 916 799	94.1
13!	6 227 020 799	14 436.6

The fast forward function skip_next_permutation uses approximately 0.009 ms for all the values.