[Haskell-cafe] Re: permuting a list

[Heinrich Apfelmus]

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]


Regards,
apfelmus

-- 
http://apfelmus.nfshost.com