[Haskell-cafe] Linear shuffle

[Ketil Malde]

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?

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