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

Groups > comp.lang.python > #45871

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

Show key headers only | View raw

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

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