Idempotent partition around median of 5?

[Timon Gehr via Digitalmars-d]

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.