[Haskell-cafe] Linear shuffle
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