Simple algorithm question - how to reorder a sequence economically

[Chris Angelico]

On Fri, May 24, 2013 at 6:14 PM, Peter Brooks
<peter.h.m.brooks at 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