Unsorting(randomizing) a sequence

[Dan Schmidt]

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/