[Haskell-beginners] Re: randomize the order of a list

[Heinrich Apfelmus]

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