random shuffles

[Ben Sizer]

Ross Ridge wrote:
> David G. Wonnacott wrote:
> > Couldn't we easily get an n*log(n) shuffle...
>
> Why are you trying to get an O(n*log(n)) shuffle when an O(n) shuffle
> algorithim is well known and implemented in Python as random.shuffle()?

I think David is referring to this: "don't you still need to use
O(log(n)) time to find and remove the item from the collection?"

The answer for him is no: as far as I know, the Python list is a
random-access structure, so looking up 2 items and swapping them runs
in constant time. You perform that N times to shuffle the sequence, so
it runs in O(N).

-- 
Ben Sizer