----------------------------------------

Date: Fri, 24 May 2013 01:14:45 -0700

Subject: Simple algorithm question - how to reorder a sequence economically

From: peter.h.m.brooks at gmail.com

To: python-list at python.org

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.

--

http://mail.python.org/mailman/listinfo/python-listI don't know what "spurious evidence of correlation" is. Can you give a mathematical definition?

Here's a snippet for creating a random shuffle by Fisher?Yates algorithm:

def FY_shuffle(l):

??? from random import randint

??? for i in range(len(l)-1,0,-1):

??????? j = randint(0,i)

??????? l[j],l[i] = l[i],l[j]

It looks just like random.shuffle() mentioned before, but you can change it as you see fit.

If you can afford to test all permutations you can iterate over it by doing:

from itertools import permutations

l=range(4)

l

[0, 1, 2, 3]

for i in permutations(l): print i

...

(0, 1, 2, 3)

(0, 1, 3, 2)

(0, 2, 1, 3)

[...]

(3, 1, 2, 0)

(3, 2, 0, 1)

(3, 2, 1, 0)

>>>

Note that 'i' is a tuple.

If you need a list of all permutations to make a selection:

[0, 1, 2, 3]

[list(i) for i in permutations(l)]

[[0, 1, 2, 3], [0, 1, 3, 2], [0, 2, 1, 3], [0, 2, 3, 1], [0, 3, 1, 2], [0, 3, 2, 1], [1, 0, 2, 3], [1, 0, 3, 2], [1, 2, 0, 3], [1, 2, 3, 0], [1, 3, 0, 2], [1, 3, 2, 0], [2, 0, 1, 3], [2, 0, 3, 1], [2, 1, 0, 3], [2, 1, 3, 0], [2, 3, 0, 1], [2, 3, 1, 0], [3, 0, 1, 2], [3, 0, 2, 1], [3, 1, 0, 2], [3, 1, 2, 0], [3, 2, 0, 1], [3, 2, 1, 0]]

This will produce big lists:

-for 10 elements (l=range(10)) the size of the list is about 30MB (on Windows).

-for 11 elements (l=range(11)) the size of the list is about 335MB (on Windows). It took more than 7GB for CPython 2.7.5 to create that list.

Didn't try after that.