Simple algorithm question - how to reorder a sequence economically

[duncan smith]

On 24/05/13 10:11, Chris Angelico wrote:
> On Fri, May 24, 2013 at 6:47 PM, Fábio Santos <fabiosantosart at gmail.com> wrote:
>>
>> On 24 May 2013 09:41, "Chris Angelico" <rosuav at gmail.com> wrote:
>>>
>>> On Fri, May 24, 2013 at 6:14 PM, Peter Brooks
>>> <peter.h.m.brooks at 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