[Haskell-cafe] Linear shuffle

[Tomasz Zielonka]

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