Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: X-Original-To: python-list@python.org Delivered-To: python-list@mail.python.org X-Spam-Status: OK 0.022 X-Spam-Evidence: '*H*': 0.96; '*S*': 0.00; 'modified': 0.07; 'subject:question': 0.10; 'cc:addr:python-list': 0.11; 'random': 0.14; 'times,': 0.14; '6:52': 0.16; 'heed': 0.16; 'implies': 0.16; 'received:74.55.86': 0.16; 'received:74.55.86.74': 0.16; 'received:smtp.webfaction.com': 0.16; 'received:webfaction.com': 0.16; 'to:addr:pearwood.info': 0.16; 'to:addr:steve+comp.lang.python': 0.16; "to:name:steven d'aprano": 0.16; 'wrote:': 0.18; 'import': 0.22; 'cc:addr:python.org': 0.22; 'header:User-Agent:1': 0.23; 'mind.': 0.24; 'cc:2**0': 0.24; 'cc:no real name:2**0': 0.24; '>': 0.26; 'this:': 0.26; 'header :In-Reply-To:1': 0.27; 'am,': 0.29; '-0700,': 0.31; "d'aprano": 0.31; 'steven': 0.31; 'tuples': 0.31; 'lists': 0.32; 'fri,': 0.33; 'not.': 0.33; 'period': 0.33; "can't": 0.35; 'but': 0.35; 'there': 0.35; 'sequence': 0.36; 'shorter': 0.36; 'subject:Simple': 0.36; 'easiest': 0.38; 'list,': 0.38; 'rather': 0.38; 'even': 0.60; 'most': 0.60; 'course': 0.61; "you'll": 0.62; 'more': 0.64; 'total': 0.65; 'different': 0.65; 'chance': 0.65; 'default': 0.69; '24.': 0.84; 'average': 0.93; '2013': 0.98 Date: Fri, 24 May 2013 07:26:00 -0400 From: Ned Batchelder User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130509 Thunderbird/17.0.6 MIME-Version: 1.0 To: Steven D'Aprano Subject: Re: Simple algorithm question - how to reorder a sequence economically References: <519f4661$0$6599$c3e8da3$5496439d@news.astraweb.com> In-Reply-To: <519f4661$0$6599$c3e8da3$5496439d@news.astraweb.com> Content-Type: multipart/alternative; boundary="------------030208000909040907090204" Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 107 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1369394778 news.xs4all.nl 15921 [2001:888:2000:d::a6]:36164 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:45876 This is a multi-part message in MIME format. --------------030208000909040907090204 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit 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. --------------030208000909040907090204 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit 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.
--------------030208000909040907090204--