Unsorting(randomizing) a sequence
Dan Schmidt
dfan at harmonixmusic.com
Tue Aug 17 16:33:38 EDT 1999
Charles G Waldman <cgw at fnal.gov> writes:
 Skip Montanaro shared:
 > Got this off the list a couple years ago. Does the trick for me:
 >
 > def shuffle(lst):
 > "randomize a list"
 > for i in range(len(lst)1,0,1):
 > choice = int(whrandom.random() * i)
 > lst[choice], lst[i] = lst[i], lst[choice]

 If you're playing poker with Skip, Jeremy, Stefan, you better let
 Stefan shuffle the cards!! The other two methods posted above are
 seriously flawed.

 By the way, Skip, I know you didn't write the "shuffle" method, just
 passed it along, but in the following I'll call it "Skip's Method"
 since I don't know who the original author is. No criticism implied.

 ...

 The "shuffle" function generates only odd or even permutations,
 depending on the sign of n. This is because at each step of the
 iteration, two elements are *always* exchanged. The means are
 monotonically increasing (the permutation tends to produce
 increasing sequences) oand the RMS variation is not equidistributed.
 It peaks (apparently) near the middle.
Skip's method is fine if choice is allowed to equal i. With that
change, element exchange is no longer forced. You can prove that
it's a perfect shuffle by induction: the last element in the shuffled
sequence has an equal chance of being any of the original elements,
and so on.
The following code implements the change:
def shuffle(lst):
"randomize a list"
for i in range(len(lst)1,0,1):
choice = int(whrandom.randint(0,i))
lst[choice], lst[i] = lst[i], lst[choice]

Dan Schmidt > dfan at harmonixmusic.com, dfan at alum.mit.edu
Honest Bob & the http://www2.thecia.net/users/dfan/
FactorytoDealer Incentives > http://www2.thecia.net/users/dfan/hbob/
Gamelan Galak Tika > http://web.mit.edu/galaktika/www/
More information about the Pythonlist
mailing list