Unsorting(randomizing) a sequence

[Guido van Rossum]

Ian Clarke <I.Clarke at strs.co.uk> writes:

> I did some timing tests using the code I have attached below, here are
> the results (in seconds) for sorting a list of 200 items 10 times:
> 
> Dan Schmidt's solution (using sort): 14.98
> Stephan Houben's solution          : 2.82
> Skip Montanaro's solution          : 2.736
>  (as modified by Dan schmidt)
> Magnus L Hetland's solution        : 0.032
> Skip's solution but with arrays    : 3.182
> 
> As you can see I thought that using arrays may provide an efficiency
> speed-up for Skip's algorithm, but apparently not.  Oh, I haven't really
> checked this code too carefully, so feel free to redo the tests if you
> find any bugs in the code.
> 
> Magnus L Hetland's solution wins hands down.

The two-orders-of-magnitude-faster result should have made you look
twice.  There's a bug: s4(list) modifies its argument (empyting it) so
you did only one run, plus 9 runs of an empty list!  Corrected, I get
these timings (on a slightly faster machine, it seems):

s1 12.1
s2 2.31
s3 2.63
s4 2.68
s5 2.82

Here's the fixed s4():

def s4(list):
    """Magnus L Hetland's solution"""
    result = []
    list = list[:]
    for i in range(len(list)):
        element = random.choice(list)
        list.remove(element)
        result.append(element)
    return result

But the winner is Tim Peters' entry, already in the CVS tree.  Its
time is 1.34 seconds:

def shuffle(x, random=random, int=int):
    """x, random=random.random -> shuffle list x in place; return None.

    Optional arg random is a 0-argument function returning a random
    float in [0.0, 1.0); by default, the standard random.random.

    Note that for even rather small len(x), the total number of
    permutations of x is larger than the period of most random number
    generators; this implies that "most" permutations of a long
    sequence can never be generated.
    """

    for i in xrange(len(x)-1, 0, -1):
        # pick an element in x[:i+1] with which to exchange x[i]
        j = int(random() * (i+1))
        x[i], x[j] = x[j], x[i]

--Guido van Rossum (home page: http://www.python.org/~guido/)