Python syntax in Lisp and Scheme

Fri Oct 10 05:11:33 CEST 2003

```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.  ;)

```