On 02/05/2016 10:13 AM, tn wrote:
On Thursday, 4 February 2016 at 20:30:57 UTC, Timon Gehr wrote:
At most 6 comparisons, <=3 swaps, idempotent (optimal number of swaps):
...
Inspired by this, I made four other versions of the function that are
shorter but make more swaps (at most 4, 6, 7 and 8 swaps respectively).
Each makes 6 comparisons and should be idempotent.
http://dpaste.dzfl.pl/1c53d8f432f7
Whoa, I missed this last night. Awesome work! Thanks! I'm kinda running
out of time budget here for this particular subproblem, but I've got to
do these justice and try them out as well.
Here are the distributions of the number of swaps when tested with all
120 possible permutations as the input:
testing 'partition5a' (by Timon Gehr)
0 swaps: 4 orderings
1 swaps: 32 orderings
2 swaps: 68 orderings
3 swaps: 16 orderings
testing 'partition5b'
0 swaps: 4 orderings
1 swaps: 20 orderings
2 swaps: 42 orderings
3 swaps: 40 orderings
4 swaps: 14 orderings
[...]
Could you please add two simple calculations? Assuming uniform random
distribution of data, compute the average number of swaps as a weighted
average of orderings. Also, show the number of lines (one test or one
swap per line) as a proxy for generated code size. That should provide
good insights.
Thanks!
Andrei
