Thursday, January 12, 2017

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.