Idempotent partition around median of 5?

[tn via Digitalmars-d]

On Saturday, 6 February 2016 at 13:06:37 UTC, Andrei Alexandrescu 
wrote:
> 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.

This now prints the numbers of comparison and swap lines and 
computes the average numbers of swaps. In addition, it also runs 
the same tests for permutations of 5 elements some of which might 
be equal (an example of such permutation would be [1, 2, 0, 2, 
3], on the other hand [1, 2, 0, 2, 4] should not be included 
since it is identical). However, in this case the average number 
of swaps is perhaps not so meaningful.

http://dpaste.dzfl.pl/2012caf872ec

Output:

testing 'partition5a'
   Code: comparisons = 63, swaps = 107, total = 170
   With all orderings of distinct elements:
     0 swaps: 4 instances
     1 swaps: 32 instances
     2 swaps: 68 instances
     3 swaps: 16 instances
     Average number of swaps: 1.8
   With all orderings of potentially nondistinct elements:
     Error, not idempotent: [0, 0, 0, 0, 0] => [0, 0, 0, 0, 0]
testing 'partition5b'
   Code: comparisons = 17, swaps = 21, total = 38
   With all orderings of distinct elements:
     0 swaps: 4 instances
     1 swaps: 20 instances
     2 swaps: 42 instances
     3 swaps: 40 instances
     4 swaps: 14 instances
     Average number of swaps: 2.33333
   With all orderings of potentially nondistinct elements:
     0 swaps: 36 instances
     1 swaps: 122 instances
     2 swaps: 200 instances
     3 swaps: 146 instances
     4 swaps: 37 instances
     Average number of swaps: 2.04806
testing 'partition5c'
   Code: comparisons = 10, swaps = 12, total = 22
   With all orderings of distinct elements:
     0 swaps: 4 instances
     1 swaps: 14 instances
     2 swaps: 25 instances
     3 swaps: 30 instances
     4 swaps: 26 instances
     5 swaps: 16 instances
     6 swaps: 5 instances
     Average number of swaps: 3.06667
   With all orderings of potentially nondistinct elements:
     0 swaps: 36 instances
     1 swaps: 92 instances
     2 swaps: 130 instances
     3 swaps: 138 instances
     4 swaps: 92 instances
     5 swaps: 42 instances
     6 swaps: 11 instances
     Average number of swaps: 2.60628
testing 'partition5d'
   Code: comparisons = 7, swaps = 8, total = 15
   With all orderings of distinct elements:
     0 swaps: 4 instances
     1 swaps: 14 instances
     2 swaps: 24 instances
     3 swaps: 29 instances
     4 swaps: 26 instances
     5 swaps: 16 instances
     6 swaps: 6 instances
     7 swaps: 1 instances
     Average number of swaps: 3.13333
   With all orderings of potentially nondistinct elements:
     0 swaps: 36 instances
     1 swaps: 100 instances
     2 swaps: 128 instances
     3 swaps: 133 instances
     4 swaps: 94 instances
     5 swaps: 39 instances
     6 swaps: 10 instances
     7 swaps: 1 instances
     Average number of swaps: 2.57486
testing 'partition5e'
   Code: comparisons = 6, swaps = 8, total = 14
   With all orderings of distinct elements:
     0 swaps: 4 instances
     1 swaps: 12 instances
     2 swaps: 19 instances
     3 swaps: 25 instances
     4 swaps: 25 instances
     5 swaps: 18 instances
     6 swaps: 11 instances
     7 swaps: 5 instances
     8 swaps: 1 instances
     Average number of swaps: 3.53333
   With all orderings of potentially nondistinct elements:
     0 swaps: 36 instances
     1 swaps: 88 instances
     2 swaps: 100 instances
     3 swaps: 123 instances
     4 swaps: 106 instances
     5 swaps: 53 instances
     6 swaps: 25 instances
     7 swaps: 9 instances
     8 swaps: 1 instances
     Average number of swaps: 2.89649