[Haskell-cafe] random shuffle and random list partition
gale at sefer.org
Tue Mar 17 07:00:14 EDT 2009
Manlio Perillo wrote:
> For my Netflix Prize project I have implemented two reusable modules.
> The first module implements a random shuffle on immutable lists...
> The second module implements a function used to partition a list into n
> sublists of random length.
> If someone is interested (and if Oleg give me permission), I can release
> them as a package on Hackage.
Please do that.
While I think Oleg's tree method is beautiful, in practice
it may be re-inventing the wheel. I haven't tested it, but
I doubt that this implementation is much better than
using the classical shuffle algorithm on an IntMap.
It's essentially the same tree inside. That's what I
usually use for this, and it works fine.
> In future I can add an implementation of the random
> shuffle algorithm on mutable arrays in the ST monad.
I've tried that in the past. Surprisingly, it wasn't faster
than using trees. Perhaps I did something wrong. Or
perhaps the difference only becomes apparent for
As you point out, your partition algorithm is not fair.
Using your Random.Shuffle and a well-know trick
from combinatorics, you can easily get a fair
More information about the Haskell-Cafe