Python syntax in Lisp and Scheme

[Andrew Dalke]

Me:
> > 2 of 6 is better than random, so Jones' work can't be
> > complete bunkum.

Jon S. Anthony:
> 2 of 6 is worse than flipping a coin.

Since I said "Of the 6 languages there are two major misorderings"
I suspect this discussion has reached the point of weariness.

Nevertheless, the ordering is 1 3 5 6 2 4

Assume a cost metric based on simple transpositions, where
neighbors can be exchanged.  This is the familiar interchange
(or Shell, or bubble, or ..) sort.  The degree of disorder is
the number of exchanges needed to sort the list.  For the
above it is ||{2-6, 2-5, 2-3, 4-6, 4-5}|| = 5

The average number of exchanges needed to sort a randomly
arranged list with the Shell sort is N*(N-1)/4 == 7.5 for
this list of size 6, so it's already better than average.

 From Knuth, Searching and Sorting, 5.1.1, Table 1, the
distribution of the number of permutations with k inversions
of a list of length 6 is
   1 way to be ordered
   5 to have one transpositions to be ordered
 14 to be off by 2 transpositions
 29
 49
 71
 90
101
101
 90
 71
 49
 29
 14
   5
   1 to be completely reversed

Thus there are 720 possible random orderings of a list of
size 6 and only 169 ways to be off by 5 or fewer transpositions.
meaning that there is only a 24% chance of being this good
randomly.

If I understand 5.1.1(13) well enough, the variance is
sqrt(6*(2*6+5)*(6-1)/72) == 2.66 which means we're
right on the 1 sigma threshold, or about a 75% chance
that his table was not randomly generated.

Again, this suggests Jones' work can't be complete
bunkum.

                    Andrew
                    dalke at dalkescientific.com
P.S.
  That's the first time in 5 years I've had to pull out Knuth.  ;)