[Haskell-cafe] Linear shuffle

Ketil Malde ketil+haskell at ii.uib.no
Fri Jan 14 04:52:53 EST 2005

Tomasz Zielonka <tomasz.zielonka at gmail.com> writes:

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

Right - this implementation picked an arbitrary element, placed it in
front, and repeated, if I understood it correctly.  Slightly different
from moving each element to a random position (e.g. after k shuffles,
elements (k+1..n) will be in the original order), but perhaps this too
can be easily emulated with an array-based (direct) shuffle?

If I haven't seen further, it is by standing in the footprints of giants

More information about the Haskell-Cafe mailing list