[Haskell-cafe] Re: permuting a list

[Heinrich Apfelmus]

Felipe Lessa wrote:
> Heinrich Apfelmus wrote:
>>
>> 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]
>>
> 
> But our sort doesn't discard values when the keys are the same. For example,
> 
> [1,2,3,4] == map snd . sortBy (compare `on` fst) . zip (repeat 1) $ [1,2,3,4]
> 
> Nothing gets duplicated. Or did I miss something?

Oops, right, elements won't be duplicated by  sortBy . I was thinking of

   randomPerm xs = zipWith (!!) xs rs


But you do loose fairness. After all, you are mapping  n^n
possibilities for  rs  to  n!  permutations and because the latter does
not divide the former, there is no way to make that balanced for general
 n .

For instance, when the sorting algorithm is stable and you want to
permute say "abcde", then 'a' is more likely to be in front of 'b'
because of those cases where both 'a' and 'b' are zipped to the same number.


Regards,
apfelmus

--
http://apfelmus.nfshost.com