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

Groups > comp.lang.python > #45896

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

Show all headers | View raw

On 24/05/13 10:11, Chris Angelico wrote:
> On Fri, May 24, 2013 at 6:47 PM, Fábio Santos <fabiosantosart@gmail.com> wrote:
>>
>> On 24 May 2013 09:41, "Chris Angelico" <rosuav@gmail.com> wrote:
>>>
>>> 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.
>>>>
>> ...
>>
>>> 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
>>
>> I think that is pretty much itertools.permutations from the standard
>> library. The OP should check it out.
>
> That works if all the permutations are wanted at once. Is there a way,
> short of iterating over it N times, to request permutation #N? Or
> maybe I'm misreading the OP and that's not a requirement.
>
> ChrisA
>

A long time ago I wrote some code to do that.


import gmpy

def LexPermFromIndex(items, index):
     n = len(items)
     inds = range(n)
     perm = []
     for i in range(1, n+1):
         r, index = divmod(index, gmpy.fac(n-i))
         r = int(r)
         perm.append(inds[r])
         inds = inds[:r] + inds[r+1:]

     return [items[i] for i in perm]


 >>> LexPermFromIndex([1,2,3,4], 0)
[1, 2, 3, 4]
 >>> LexPermFromIndex([1,2,3,4], 1)
[1, 2, 4, 3]
 >>> LexPermFromIndex([1,2,3,4], 10)
[2, 4, 1, 3]
 >>>


I can't remember exactly why I wrote it. But I also have something for 
generating a permutation's index and similar functions for combinations.

Duncan

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