[Haskell-cafe] Linear shuffle
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.
More information about the Haskell-Cafe