HTTPS SSH

Stack sorting and fertility numbers

This is a c++ implementation of Julian Wests stack sorting algorithm described in "Permutations with restricted subsequences and stack-sortable permutations".

The purpose is to generate fertility numbers, for more info see my post or this pdf.

In order to keep the memory consumption down I had to replace std::unordered_map with tsl::sparse_map, which is working great! Another thing I had to do was to encode the sorted output permutation into a 64 bit long, giving 4 bits to each terminal.

Challange: get this to complete for n=15

With n=14 it takes about 16GB ram and 5-6 hours to complete (if I recall correctly).

If you have a 64GB machine it should be possible to pull n=15 off, one way might be to flush the map to a sorted vector every now and then.

Keeping each entry in the vector at 12 bytes (8+4) (you might need to use #pragma pack(1)) will require about 53GB of memory giving you some margin.

I am not sure how long it would take to run, but lookups will be slower, there are now 2 of them (O(logn)+O(1)) also the overhead of the flusing and sorting of the vector.

Let me know if you are interested in helping me out, or if you manage to run it, please send me the found numbers :)