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[idx1] * 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.
No comments:
Post a Comment