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

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>.

 

[Bill Mill]

Tim's solution is very nice, it comes from basic things often taught in
good computer science courses.

I dunno, that comes from my Abstract Algebra course a heck of a lot
more than it came from any of my CS classes (I graduated last May)

While I'm at it though, I want to thank Tim for that post. It was one
of those posts where afterwards you say "of course!" but beforehand I
was totally thinking of it the wrong way. Brought me right back to
Abstract.

Peace
Bill Mill
bill.mill at gmail.com

 

[Bill Mill]

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>.

That's where you get to leave comments like:

#it follows logically that
assert j not in seen

or

#by implication
assert j not in seen

just to really frustrate the guy reading your code.

Peace
Bill Mill
bill.mill at gmail.com