[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>.
--
http://mail.python.org/mailman/listinfo/python-list
