On 02/05/2016 10:42 PM, Xinok wrote:
On Friday, 5 February 2016 at 15:13:56 UTC, 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
...
Very nice! I'm curious, to both you and Timon, how did you go about
writing these and coming up with the solutions? I'm not sure if I could
come up with these results myself and so quickly at that.
I quickly hacked together a brute-force search.
Code: http://dpaste.dzfl.pl/43503913ac1d
The search only makes sure that it works for distinct input values.
Other input orders come for free; the verification code I have included
checks this.
The code recursively splits the set of all permutations on 5 elements by
all possible comparisons between two elements up to a maximal depth of 6
comparisons, using some basic pruning. The recursion terminates if all
permutations in the set can be partitioned using the same swaps. (I.e.,
the index of the median is fixed and there are exactly two possible
indices for the first two elements, and exactly two possible indices for
the last two elements.)
The partition5 function I have posted is the first result that the
search found. The above code also supports optimizing for source code
size (-version=SHORT). The result is not that much shorter though.
