Path: csiph.com!usenet.pasdenom.info!news.albasani.net!newsfeed.freenet.ag!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <a31c773f-88d8-4489-8640-12123d884e4d@m2g2000vbb.googlegroups.com>
References: <a31c773f-88d8-4489-8640-12123d884e4d@m2g2000vbb.googlegroups.com>
Date: Fri, 24 May 2013 18:37:49 +1000
Subject: Re: Simple algorithm question - how to reorder a sequence economically
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.2051.1369384673.3114.python-list@python.org>
Lines: 66
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:45871

On Fri, May 24, 2013 at 6:14 PM, Peter Brooks
<peter.h.m.brooks@gmail.com> wrote:
> What is the easiest way to reorder a sequence pseudo-randomly?
>
> That is, for a sequence 1,2,3,4 to produce an arbitrary ordering (eg
> 2,1,4,3) that is different each time.
>
> I'm writing a simulation and would like to visit all the nodes in a
> different order at each iteration of the simulation to remove the risk
> of a fixed order introducing spurious evidence of correlation.

Permuting a sequence iteratively to cover every possibility? Good fun.

Here's one way of looking at it. Imagine the indices of all elements
are in some special "base" like so:

[a, b, c, d] --> a*4+b*3+c*2+d*1

Then iterate up to the highest possible value (ie 4*3*2*1), picking
indices for each accordingly. I don't know how efficient this will be,
but here's a simple piece of code to do it:

>>> def permute(lst,pos):
	lst=lst[:] # Take a copy
	ret=[None]*len(lst)
	for i in range(len(lst)):
		pos,idx=divmod(pos,len(lst))
		ret[i]=lst[idx]
		del lst[idx]
	return ret

>>> for i in range(4*3*2*1):
	permute([10,20,30,40],i)

	
[10, 20, 30, 40]
[20, 10, 30, 40]
[30, 10, 20, 40]
[40, 10, 20, 30]
[10, 30, 20, 40]
[20, 30, 10, 40]
[30, 20, 10, 40]
[40, 20, 10, 30]
[10, 40, 20, 30]
[20, 40, 10, 30]
[30, 40, 10, 20]
[40, 30, 10, 20]
[10, 20, 40, 30]
[20, 10, 40, 30]
[30, 10, 40, 20]
[40, 10, 30, 20]
[10, 30, 40, 20]
[20, 30, 40, 10]
[30, 20, 40, 10]
[40, 20, 30, 10]
[10, 40, 30, 20]
[20, 40, 30, 10]
[30, 40, 20, 10]
[40, 30, 20, 10]

It works, it produces a unique list for any given index provided, but
it's not the cleanest or most efficient. But I know someone'll improve
on it... or tell me I'm an idiot for not taking a more obvious
approach :)

ChrisA