sorting a list and counting interchanges

[Tim Peters]

[Paul Rubin]
> Writing a sorting function from scratch for this purpose seems like
> reinventing the wheel.

Yup!  list.sort() is going to be mounds faster.

> Tim's answer of simply counting the cycles (without having to pay
> attention to their length) is really clever.  I didn't realize you could do
> that.

It's a standard trick; see, e.g., Nijenhuis & Wilf's "Combinatorial
Algorithms" -- although it can be hard to extract the _sense_ out of
clever Fortran <0.7 wink>.

> Proving it is a cute exercise.  Hint: any cycle of odd length has an even
> number of swaps, and any cycle of even length has an odd number of swaps
> (another exercise).

More precisely, a cycle of length c can be written as the product of
c-1 transpositions.  If the permutation is the product of m disjoint
cycles of lengths c_1, c_2, ..., c_m, then decomposing those into
transpositions gives a total number of transpositions:

    (c_1-1) + (c_2-1) + ... + (c_m-1) =  [rearranging and combining the m 1's]
    (c_1 + c_2 + ... + c_m) - m = [each element appears exactly once in
                                                one cycle, since the
cycles are disjoint]
    number_of_elements - m

which the code spelled

    n - num_cycles

I think it's harder for some people to see why the

    assert j not in seen

must be true, although that's obvious after just a few hours' thought <wink>.