[Haskell-cafe] Linear shuffle

Tomasz Zielonka tomasz.zielonka at gmail.com
Fri Jan 14 04:22:29 EST 2005

On Fri, Jan 14, 2005 at 10:17:27AM +0100, Ketil Malde wrote:
> Tomasz Zielonka <tomasz.zielonka at gmail.com> writes:
> > On Fri, Jan 14, 2005 at 09:17:41AM +0100, Gracjan Polak wrote:
> >> This algorithm seems not effective, length, take, drop and (!!) are 
> >> costly. Is there any better way to implement shuffle?
> > You can use mutable arrays (modules Data.Array.MArray, Data.Array.IO). 
> But is that better, really?  IIUC, you will now need to shift the first
> part of the string to the right, so it's still a linear operation for
> each shuffle.

Perhaps I don't know this particular algorithm, but you can shuffle the
array with linear number of swaps. No need to shift elements.

Best regards,

More information about the Haskell-Cafe mailing list