[Haskell-beginners] Re: randomize the order of a list
John Dorsey
haskell at colquitt.org
Sun Sep 12 14:43:15 EDT 2010
Heinrich Apfelmus wrote:
> Why should it be uniform just because it looks nice? Looks can be
> deceiving, you need a mathematical proof to be certain.
My claim was that it is "uniform and simple"; naturally neither follows from
the other, but each has merit.
> Embarrassingly, the analysis in my previous message is wrong, though.
> Here an actually correct assessment of the algorithm. Or rather, of the
> two algorithms; the results are different depending on whether you use a
> pivot *element* or just a pivot *position*. It will turn out that the
> former is not uniform, while, to my surprise, the latter is uniform!
And this was my point. I never considered a pivot *element*, which you
correctly point out wouldn't work so well. I was referring to a pivot taken
from a randomly chosen *position*. On re-reading Gabriel Scherer's original
musing:
>>>> Thanks for the link apfelmus, it's fairly interesting. The key to
>>>> making it work is the weighting of lists during merging based on their
>>>> lengths. I wonder if other sort algorithm can be adapted in such a
>>>> way, while preserving uniformity. Quicksort for example : is it enough
>>>> to choose the result position of the pivot randomly, and then placing
>>>> elements on either side with a probability of 1/2 ?
I may have misunderstood his original intent, as he refers to a random
"result position" for a pivot (chosen how?). But if that's changed to
choosing the pivot from a random position, then it works out nicely. I
think you agree with this later in your email.
And finally, re-reading your earlier comment:
>>> First, you can skip choosing the pivot position because it is already
>>> entailed by the choices of elements left and right to it.
I think I understand now what you were referring to... (redundantly)
choosing the destination for a pivot chosen by some other unspecified means.
It seems we were talking beside each other; I'm sorry if I misunderstood
you earlier.
Cheers,
John Dorsey
More information about the Beginners
mailing list