Unsorting(randomizing) a sequence

[Stephan Houben]

Dan Schmidt <dfan at harmonixmusic.com> writes:

> Charles G Waldman <cgw at fnal.gov> writes:
> 
> 
> 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]

Note that this is almost equivalent to "my" algorithm (which I now
repeat for the ease of the reader):

def randomize(l): 
    length = len(l) 
    for i in range(length): 
        j = rand.randrange(i, length) 
        l[i], l[j] = l[j], l[i]

The only difference is that Skip's method, as modified by Charles,
(which makes it Charles' method, I guess) lets i walk downwards
and picks elements from the first part of the list, whereas my
method has i walking upwards and picks elements from the last part
of the list. So my method could be converted into Charles' method by
reverting the list first. But since they both randomize the list,
the original order of the list shouldn't matter.

Furthermore, Skip used he module whrandom, whereas I used random.
Any ideas in which respect these modules differ?

Finally, the use of int(...) in the 4th line of Skip's/Charles' method
seems superfluous to me.

And finally finally, perhaps a teenie weenie speed increase can still
be had by using:

def randomize(l): 
    randrange = rand.randrange
    length = len(l) 
    for i in range(length): 
        j = randrange(i, length) 
        l[i], l[j] = l[j], l[i]

,so that only local variables are used inside the inner loop.
But I didn't test whether this actually buys you anything speedwise.
And it makes the algorithm longer.

Greetings,

Stephan