[Haskell-cafe] Re: permuting a list

[Alberto Ruiz]

Heinrich Apfelmus wrote:
> Jon Fairbairn wrote:
>> Heinrich Apfelmus writes:
>>
>>> The answer is a resounding "yes" and the main idea is that shuffling a
>>> list is *essentially the same* as sorting a list; the minor difference
>>> being that the former chooses a permutation at random while the latter
>>> chooses a very particular permutation, namely the one that sorts the input.
>>>
>>> For the full exposition, see
>>>
>>>    http://apfelmus.nfshost.com/random-permutations.html
>> I haven't been following the thread, but my initial reaction
>> would have been something like use System.Random.randoms to
>> get a list rs and then do (roughly)
>>
>> randomPerm = map snd . sortBy (compare `on` fst) . zip rs
>>
>> How bad is that? I mean, how unfair does it get?
> 
> It's fair, but may duplicate elements, i.e. it doesn't necessarily
> create a permutation. For example,  rs  could be something like
> 
>    rs = [5,3,3,3,2,4]
> 

How about using random doubles?

randomPerm xs = fmap (map snd . sort . flip zip xs) rs
     where rs = fmap (randoms . mkStdGen) randomIO :: IO [Double]