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/
Factory-to-Dealer Incentives -> http://www2.thecia.net/users/dfan/hbob/
Gamelan Galak Tika -> http://web.mit.edu/galak-tika/www/
More information about the Python-list
mailing list