Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!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.003 X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'algorithm': 0.04; '-for': 0.05; 'cpython': 0.05; '[0,': 0.09; '[1,': 0.09; 'iterate': 0.09; 'snippet': 0.09; 'subject:question': 0.10; 'def': 0.12; 'random': 0.14; '(0,': 0.16; '(3,': 0.16; '0],': 0.16; '2],': 0.16; '3],': 0.16; '[2,': 0.16; 'correlation.': 0.16; 'doing:': 0.16; 'iteration': 0.16; 'itertools': 0.16; 'nodes': 0.16; 'spurious': 0.16; 'subject: \n ': 0.16; 'tuple.': 0.16; 'elements': 0.16; '>>>': 0.22; 'import': 0.22; 'to:name:python-list@python.org': 0.22; 'print': 0.22; 'creating': 0.23; 'mathematical': 0.24; 'received:65.55.116': 0.24; 'looks': 0.24; 'question': 0.24; 'header:In-Reply-To:1': 0.27; 'fixed': 0.29; 'skip:- 40': 0.29; "i'm": 0.30; 'url:mailman': 0.30; 'that.': 0.31; '(on': 0.31; 'url:python': 0.33; 'fri,': 0.33; 'date:': 0.34; 'test': 0.35; 'but': 0.35; 'introducing': 0.36; 'sequence': 0.36; 'subject:Simple': 0.36; 'url:listinfo': 0.36; "didn't": 0.36; 'url:org': 0.36; 'list': 0.37; 'email addr:python.org': 0.37; 'list.': 0.37; 'easiest': 0.38; 'to:addr:python-list': 0.38; 'subject:': 0.39; '\xa0\xa0\xa0': 0.39; 'to:addr:python.org': 0.39; 'url:mail': 0.40; 'how': 0.40; 'remove': 0.60; 'is.': 0.60; 'mentioned': 0.61; 'took': 0.61; 'simple': 0.61; 'email addr:gmail.com': 0.63; 'visit': 0.64; 'more': 0.64; 'different': 0.65; 'email name:python-list': 0.65; 'charset:windows-1252': 0.65; 'risk': 0.72; 'afford': 0.91; 'lists:': 0.91; 'simulation': 0.91; '2013': 0.98 X-TMN: [zH/cJZ4YlsIJw08tnHw13iqMgXBE3Nvu] X-Originating-Email: [carlosnepomuceno@outlook.com] From: Carlos Nepomuceno To: "python-list@python.org" Subject: RE: Simple algorithm question - how to reorder a sequence economically Date: Fri, 24 May 2013 18:00:59 +0300 Importance: Normal In-Reply-To: References: Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginalArrivalTime: 24 May 2013 15:00:59.0568 (UTC) FILETIME=[8041B300:01CE588F] 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: 76 NNTP-Posting-Host: 2001:888:2000:d::a6 X-Trace: 1369407666 news.xs4all.nl 15864 [2001:888:2000:d::a6]:57441 X-Complaints-To: abuse@xs4all.nl Xref: csiph.com comp.lang.python:45897 ----------------------------------------=0A= > Date: Fri=2C 24 May 2013 01:14:45 -0700=0A= > Subject: Simple algorithm question - how to reorder a sequence economical= ly=0A= > From: peter.h.m.brooks@gmail.com=0A= > To: python-list@python.org=0A= >=0A= > What is the easiest way to reorder a sequence pseudo-randomly?=0A= >=0A= > That is=2C for a sequence 1=2C2=2C3=2C4 to produce an arbitrary ordering = (eg=0A= > 2=2C1=2C4=2C3) that is different each time.=0A= >=0A= > I'm writing a simulation and would like to visit all the nodes in a=0A= > different order at each iteration of the simulation to remove the risk=0A= > of a fixed order introducing spurious evidence of correlation.=0A= > --=0A= > http://mail.python.org/mailman/listinfo/python-list=0A= =0A= I don't know what "spurious evidence of correlation" is. Can you give a mat= hematical definition?=0A= =0A= Here's a snippet for creating a random shuffle by Fisher=96Yates algorithm:= =0A= =0A= def FY_shuffle(l):=0A= =A0=A0=A0 from random import randint=0A= =A0=A0=A0 for i in range(len(l)-1=2C0=2C-1):=0A= =A0=A0=A0=A0=A0=A0=A0 j =3D randint(0=2Ci)=0A= =A0=A0=A0=A0=A0=A0=A0 l[j]=2Cl[i] =3D l[i]=2Cl[j]=0A= =0A= It looks just like random.shuffle() mentioned before=2C but you can change = it as you see fit.=0A= =0A= If you can afford to test all permutations you can iterate over it by doing= :=0A= =0A= >>> from itertools import permutations=0A= >>> l=3Drange(4)=0A= >>> l=0A= [0=2C 1=2C 2=2C 3]=0A= >>> for i in permutations(l): print i=0A= ...=0A= (0=2C 1=2C 2=2C 3)=0A= (0=2C 1=2C 3=2C 2)=0A= (0=2C 2=2C 1=2C 3)=0A= [...]=0A= (3=2C 1=2C 2=2C 0)=0A= (3=2C 2=2C 0=2C 1)=0A= (3=2C 2=2C 1=2C 0)=0A= >>>=0A= =0A= Note that 'i' is a tuple.=0A= =0A= If you need a list of all permutations to make a selection:=0A= =0A= >>> l=3Drange(4)=0A= >>> l=0A= [0=2C 1=2C 2=2C 3]=0A= >>> [list(i) for i in permutations(l)]=0A= [[0=2C 1=2C 2=2C 3]=2C [0=2C 1=2C 3=2C 2]=2C [0=2C 2=2C 1=2C 3]=2C [0=2C 2= =2C 3=2C 1]=2C [0=2C 3=2C 1=2C 2]=2C [0=2C 3=2C 2=2C 1]=2C [1=2C 0=2C 2=2C = 3]=2C [1=2C 0=2C 3=2C 2]=2C [1=2C 2=2C 0=2C 3]=2C [1=2C 2=2C 3=2C 0]=2C [1= =2C 3=2C 0=2C 2]=2C [1=2C 3=2C 2=2C 0]=2C [2=2C 0=2C 1=2C 3]=2C [2=2C 0=2C = 3=2C 1]=2C [2=2C 1=2C 0=2C 3]=2C [2=2C 1=2C 3=2C 0]=2C [2=2C 3=2C 0=2C 1]= =2C [2=2C 3=2C 1=2C 0]=2C [3=2C 0=2C 1=2C 2]=2C [3=2C 0=2C 2=2C 1]=2C [3=2C= 1=2C 0=2C 2]=2C [3=2C 1=2C 2=2C 0]=2C [3=2C 2=2C 0=2C 1]=2C [3=2C 2=2C 1= =2C 0]]=0A= =0A= This will produce big lists:=0A= -for 10 elements (l=3Drange(10)) the size of the list is about 30MB (on Win= dows).=0A= -for 11 elements (l=3Drange(11)) the size of the list is about 335MB (on Wi= ndows). It took more than 7GB for CPython 2.7.5 to create that list.=0A= =0A= Didn't try after that. =