John Dorsey wrote:
Heinrich Apfelmus wrote:
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 probably helps to write down some code for the different possibilities. :) * Pivot element, position chosen by a dice roll. This is closest to quicksort in spirit. quickshuffle (x:xs) = do k <- uniform [0..length xs] (ls,rs) <- partition k xs -- satisfies length ls == k sls <- quickshuffle ls srs <- quickshuffle rs return (ls ++ [x] ++ rs) * Pivot element, position fixed. This is Gabriel's solution. quickshuffle (x:xs) = do let k = length xs `div` 2 (ls,rs) <- partition k xs -- satisfies length ls == k sls <- quickshuffle ls srs <- quickshuffle rs return (ls ++ [x] ++ rs) * Pivot element, position entailed by the random partition. quickshuffle (x:xs) = do (ls,rs) <- partition xs sls <- quickshuffle ls srs <- quickshuffle rs return (ls ++ [x] ++ rs) * Pivot position, chosen by a dice roll. The arguments to the recursive calls to quickshuffle are no longer guaranteed to be smaller; the algorithm might run for an arbitrarily long time. quickshuffle xs = do k <- uniform [0..length xs] (ls,rs) <- partition k xs -- satisfies length ls == k sls <- quickshuffle ls srs <- quickshuffle rs return (ls ++ rs) * Pivot position, entailed by the random partition. This is the only algorithm where picking elements to the left or the right with probability 1/2 gives a uniform permutation. Same problem with potentially arbitrarily long running times, though. quickshuffle xs = do (ls,rs) <- partition xs sls <- quickshuffle ls srs <- quickshuffle rs return (ls ++ rs) The partition functions needed to get permutations with uniform probability are quite different for the different algorithms. Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com