Random picks from permutation generator?

Question

How to randomly pick all the results, one by one (no repeats) from itertools.permutations(k)? Or this: how to build a generator of randomized permutations? Something like shuffle(permutations(k)). I’m using Python 2.6.

Yeah, shuffle(r) could be used if r = list(permutations(k)), but such a list will take up too much time and memory when len(k) raises above 10.

Thanks.

Answer 1

this gives the nth permutation of a list

def perm_given_index(alist, apermindex):
    alist = alist[:]
    for i in range(len(alist)-1):
        apermindex, j = divmod(apermindex, len(alist)-i)
        alist[i], alist[i+j] = alist[i+j], alist[i]
    return alist

where apermindex is between 0 and factorial(len(alist))

Answer 2

I don't know how python implements its shuffle algorithm, but the following scales in linear time, so I don't see why a length of 10 is such a big deal (unless I misunderstand your question?):

• start with the list of items;
• go through each index in the list in turn, swapping the item at that index it for an item at a random index (including the item itself) in the remainder of the list.

For a different permutation, just run the same algorithm again.