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; std::vector<uint64_t> factorials;
factorials.push_back(1); long idx = 1;
long input_length = end  begin;
do {
factorials.push_back(factorials[idx1] * idx);
} while (factorials[++idx  1] <= skip_num); we want to skip forward
long my_inc = factorials.size()  2;
do
{
int quotient = skip_num / factorials[my_inc];
skip_num = skip_num%factorials[my_inc];
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); 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.