[Haskell-cafe] Re: permuting a list
apfelmus at quantentunnel.de
Sun Feb 15 07:54:15 EST 2009
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
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.
More information about the Haskell-Cafe