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.

Answer 3

There's no way of doing what you have asked for without writing your own version of permutations.

Consider this:

• We have a generator object containing the result of permutations.
• We have written our own function to tell us the length of the generator.
• We then pick an entries at random between the beginning of the list and the end.

Since I have a generator if the random function picks an entry near the end of the list the only way to get to it will be to go through all the prior entries and either throw them away, which is bad, or store them in a list, which you have pointed out is problematic when you have a lot of options.

Are you going to loop through every permutation or use just a few? If it's the latter it would make more sense to generate each new permutation at random and store then ones you've seen before in a set. If you don't use that many the overhead of having to create a new permutation each time you have a collision will be pretty low.

Answer 4

There are algorithms that can give you permutations. You can find one that works in linear time in this wikipedia article.

Implement it in python using yield for efficient sequential generation. Though, if you want random picking with no repetitions, you'll have to generate the list, or use the algorithm posted by Dan and remember numbers you already chose.

Answer 5

What you're looking for is the Lehmer index. The Lehmer index can be generated from a random integer and can then be turned into a specific permutation, all without the need to generate a set of permutations only one of which you actually use.

Knowing that you want one of the n-permutations of n objects, you know that there are n! of them. All you would need to do is choose a number between 0 and n!-1 and use the Lehmer code to translate your base-10 index into the Lehmer code, which would then become a factorial base number. These numbers are also known as factoradics.

Say for example that you want to choose a specific random permutation of 3 objects indexed 0, 1, and 2. The Lehmer code for (0, 1, 2) (all in order) would be (0, 0, 0), where the first two zeros are all that matter since the last zero is the 0! place which is always zero. So just consider the first two. Then the Lehmer code for permutation (0, 1, 2) would be (0, 0) because the number of inversions in each subset of numbers is 0, i.e. (0, 1, 2) has no inversions (because 0 < 1 < 2) and (1, 2) has no inversions (because 1 < 2).

Another example would be (2, 1, 0). To get the Lehmer code for this one, you would count inversions in the same way. There are 2 inversion in (2, 1, 0) as a whole (because 2 > 1 and 1 > 0) and there is 1 in version in the sub-permutation (1, 0) (because 1 > 0). So this would give (2, 1) as the Lehmer code. If we add on the zero which is always there then this would make the Lehmer code (2, 1, 0).

So how would you use this? Every Lehmer code has a base-10 number that corresponds to it because each number position has a place value. In the case of (2, 1, 0) from above, we have 2 * 2! + 1 * 1! + 0 * 0! = 4 + 1 + 0 = 5. Now you can choose a random number, like 5, and produce the Lehmer code and then the specific permutation without generating them all.

Here's some code I wrote a while back to do just this. It refers to the Lehmer code as radix, just so there's no confusion. This is from my util repository on GitHub.

/**
 * Given a factoradic index, this function computes the radix form of the
 * index. That is, it converts the base 10 input index into a non-constant
 * factorial base number.
 */
long int factoradic_radix_index_long( long int dim_in, long int idx_in, long int *rad_out )
{
    long int i,fct,div,rem;

    rem = idx_in;
    for(i=dim_in-1;i>=0;i--)
    {
        fct = factorial( i );
        div = rem / fct;
        rem = rem % fct;
        rad_out[dim_in-1-i] = div;
    }
}

To see how you get the actual permutation from the radix vector (Lehmer code), here's a sample which does the whole conversion from base-10 permutation index to permutation.

long int factoradic_vector_long( long int idx_in, long int dim_in, long int *vec_out )
{
    long int i,j,k,rad[dim_in];
    int fnd[dim_in];

    for(i=0;i<dim_in;i++)
        fnd[i] = 0;

    factoradic_radix_index_long( dim_in, idx_in, rad );

    for(i=0;i<dim_in;i++)
    {
        for(j=0,k=0;j<dim_in;j++)
        {
            if( fnd[j] == 0 )
                ++k;
            if( k - 1 >= rad[i] )
                break;
        }
        fnd[j] = 1;
        vec_out[i] = j;
    }
    return 0;
}

Answer 6

Perhaps that's not so efficient, but it allows to deal with any number of random permutations the given list.

import numpy as np
from math import factorial

for i in range(factorial(len(biglist))):
    permut = np.random.permutation(biglist).tolist()
    ...