Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #45897

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

Show all headers | View raw

----------------------------------------
> Date: Fri, 24 May 2013 01:14:45 -0700
> Subject: Simple algorithm question - how to reorder a sequence economically
> From: peter.h.m.brooks@gmail.com
> To: python-list@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. 		 	   		  

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Simple algorithm question - how to reorder a sequence economically Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-24 01:14 -0700
  Re: Simple algorithm question - how to reorder a sequence economically Chris Angelico <rosuav@gmail.com> - 2013-05-24 18:37 +1000
  Re: Simple algorithm question - how to reorder a sequence economically Fábio Santos <fabiosantosart@gmail.com> - 2013-05-24 09:47 +0100
  Re: Simple algorithm question - how to reorder a sequence economically Chris Angelico <rosuav@gmail.com> - 2013-05-24 19:11 +1000
    Re: Simple algorithm question - how to reorder a sequence economically duncan smith <buzzard@invalid.invalid> - 2013-05-24 15:33 +0100
  Re: Simple algorithm question - how to reorder a sequence economically Terry Jan Reedy <tjreedy@udel.edu> - 2013-05-24 06:10 -0400
  Re: Simple algorithm question - how to reorder a sequence economically Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-24 10:52 +0000
    Re: Simple algorithm question - how to reorder a sequence economically Ned Batchelder <ned@nedbatchelder.com> - 2013-05-24 07:26 -0400
      Re: Simple algorithm question - how to reorder a sequence economically Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-24 06:23 -0700
        Re: Simple algorithm question - how to reorder a sequence economically Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-05-24 13:57 +0000
        Re: Simple algorithm question - how to reorder a sequence economically Robert Kern <robert.kern@gmail.com> - 2013-06-12 14:14 +0100
    Re: Simple algorithm question - how to reorder a sequence economically John Ladasky <john_ladasky@sbcglobal.net> - 2013-05-24 10:33 -0700
      Re: Simple algorithm question - how to reorder a sequence economically John Ladasky <john_ladasky@sbcglobal.net> - 2013-05-25 18:25 -0700
        Re: Simple algorithm question - how to reorder a sequence economically Roy Smith <roy@panix.com> - 2013-05-25 21:49 -0400
  RE: Simple algorithm question - how to reorder a sequence economically Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-24 18:00 +0300
    Re: Simple algorithm question - how to reorder a sequence economically Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-24 12:01 -0700
      RE: Simple algorithm question - how to reorder a sequence economically Carlos Nepomuceno <carlosnepomuceno@outlook.com> - 2013-05-25 00:33 +0300
        Re: Simple algorithm question - how to reorder a sequence economically Peter Brooks <peter.h.m.brooks@gmail.com> - 2013-05-24 17:28 -0700

csiph-web