Simple algorithm question - how to reorder a sequence economically

[Carlos Nepomuceno]

----------------------------------------
> 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-list

I 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:

>>> l=range(4)
>>> l
[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.