Quickselect and the number of cycles.

[Marko Riedel <markoriedelde@yahoo.de>]

Greetings.

The inversion count is a measure of the amount of
disorder in a permutation. The higher the inversion
count, the more disordered is the permutation.

A different measure of disorder in a permutation is
the number of cycles. The more cycles there are, the
more ordered is the permutation.

Question. Compute the grand average of the expected
number of cycles of a random permutation after a
random element has been selected with quickselect. The
recursion step decomposes very nicely. Compare and
contrast with the expected number of cycles of a
random permutation.

I wonder who will be the first to post and solve the
appropriate DE? Adelante! Auf die Plaetze, fertig,
los!

;-)

Best regards,

Marko Riedel



__________________________________________________________________
Do You Yahoo!?
Gesendet von Yahoo! Mail - http://mail.yahoo.de