Python-list Digest, Vol 34, Issue 373

[David G. Wonnacott]

O.K., I'll publicly retract this for the whole list -- EVERYBODY
PLEASE DISREGARD my thought about implementing an n*log(n) shuffle.

I had hinted in my message that this was probably something that I
should review from a data structures course, and of course there was a
simple oversight in my message: you don't have to preserve the order
of the collection from which you extract the element, so you can
extract it in O(1) time by just swapping it, and easily get an O(n)
shuffle algorithm (or, more easily, call random.shuffle()).

Thanks for the polite tone with which many folks have pointed out my
gross oversight.

for i in range(1,100):
    print "I will not post to the Python list without thinking first"

Now suitably embarrassed,
			Dave Wonnacott


   Date: 24 Jul 2006 06:24:48 -0700
   From: "Ben Sizer" <kylotan at gmail.com>
   Subject: Re: random shuffles
   To: python-list at python.org

   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