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