[Haskell-cafe] random shuffle and random list partition

[Yitzchak Gale]

Hi Manlio,

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.

Very nice!

> 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
huge lists.

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
partitions function:

http://hpaste.org/fastcgi/hpaste.fcgi/view?id=2485#a2495

Regards,
Yitz