Re: [Haskell-cafe] Linear shuffle

On Fri, Jan 14, 2005 at 10:17:27AM +0100, Ketil Malde wrote:

Tomasz Zielonka 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, Tomasz