Simple algorithm question - how to reorder a sequence economically

[Ned Batchelder]

On 5/24/2013 6:52 AM, Steven D'Aprano wrote:
> On Fri, 24 May 2013 01:14:45 -0700, Peter Brooks wrote:
>
>> What is the easiest way to reorder a sequence pseudo-randomly?
> import random
> random.shuffle(sequence)
>
>
> The sequence is modified in place, so it must be mutable. Lists are okay,
> tuples are not.
>
>
>> That is, for a sequence 1,2,3,4 to produce an arbitrary ordering (eg
>> 2,1,4,3) that is different each time.
> You can't *guarantee* that it will be different each time. With a four-
> item list, there are only 4! = 24 combinations, so on average you'll get
> the original order one time in 24. For a ten-item list, that is once
> every 3628800 times, and for a twenty-item list, once in
> 2432902008176640000 times. But of course these are *random*, and there's
> always a chance of this:
>
> http://dilbert.com/strips/comic/2001-10-25
>
>

Also, heed the note in the docs:  "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."  The default 
random number generator has a period of 2**19937-1, which means that 
lists longer than 2080 have more permutations than the period of the 
generator (because factorial(2081) > 2**19937). Most shuffles involve 
lists far shorter than 2080, but it's still good to keep it in mind.

--Ned.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20130524/630b2e0b/attachment.html>