How to generate permutations of array in python?

Question

I have an array of 27 elements, and I don't want to generate all permutations of array (27!) I need 5000 randomly choosed permutations, any tip will be useful...

• Mark Byers: It might be worth mentioning that 27! is 10888869450418352160768000000.

Answer 1

To generate one permutation use random.shuffle and store a copy of the result. Repeat this operation in a loop and each time check for duplicates (there probably won't be any though). Once you have 5000 items in your result set, stop.

To address the point in the comment, Python's random module is based on the Mersenne Twister and has a period of 2**19937-1, which is considerably larger than 27! so it should be suitable for your use.

• John Feminella: +1, but note that random.shuffle has a serious weakness: the period of most RNGs is smaller than the total number of permutations as n gets larger. That means that almost all of the possible permutations for a large enough n cannot ever be generated, so this isn't truly random.
• Mark Byers: Indeed, John. Python's random generator has a period of 2**19937-1 though so it is probably good enough. Another nitpick is that for true random numbers you would need a true random source (e.g. from radioactive decay), Python's random module provides only pseudo-random numbers. But in common usage when people say 'random' what they really mean is 'pseudo-random', and I assume this is what the poster here means.
• Pratik Deoghare: +1 Cool! It's a big die with 10888869450418352160768000000 faces probability of any one of them turning up is 1/10888869450418352160768000000. Duplicates NO WAY!!
• wizzwizz4: @PratikDeoghare It's a big die with a 6002-digit number of faces, but it rotates in a specific, known pattern and loads of the faces have the same number on. Duplicates yes way.
• matteo_c: The probability that any one of them is equal to another is 1/10888869450418352160768000000, but the probability that none of them is the same is bigger. For example, if you take 27!+1 permutations, even if the probability that one of them is equal to another is small, the probability that there's no duplicate is 0. In this case, beacause 27! >> 5000, the probability that there's at least a duplicate is (1/27)*5000. Still small, but it isn't the same.

Answer 2

import random
perm_list = []
for i in range(5000):
 temp = range(27)
 random.shuffle(temp)
 perm_list.append(temp)
print(perm_list)

10888869450418352160768000000 I love big numbers! :)

AND

10888869450418352160768000001 is PRIME!!

EDIT:

#with duplicates check as suggested in the comment
perm_list = set()
while len(perm_list)<5000:
 temp = range(27)
 random.shuffle(temp)
 perm_list.add(tuple(temp)) # `tuple` because `list`s are not hashable. right Beni?
print perm_list

WARNING: This wont ever stop if RNG is bad!

• Beni Cherniavsky-Paskin: To also check for duplicates as Mark suggests, use a perms = set(), perms.add(tuple(temp)), and while len(perms) < 5000 instead of the for loop.
• Pratik Deoghare: @Beni I didn't follow your tuple(temp) suggestion at first but then I understood that I was a fool!! Thanks man!

Answer 3

itertools.permutations. It's a generator, so it won't create the whole list of permutations. You could skip randomly until you've got 5000.

• John Feminella: That's not really "random", since itertools creates them in a defined order, and there are a finite number of permutations. What would be better is to do the following: (1) determine how many permutations there are (call this number N), (2) then generate 5,000 distinct random indices in the range 0..N-1, (3) pick the permutations from the itertools.permutations generator which correspond to these indices.
• Cat Plus Plus: Yeah, I know it's not the best. First time I read the question I somehow didn't notice that 'randomly chosen' part. I won't delete it, maybe someone searching for "how to generate permutations of array in python?" will find it useful.
• Shon Freelen: @Cat Plus Plus That would be me :D

Answer 4

# apermindex should be a number between 0 and factorial(len(alist))
def perm_given_index(alist, apermindex):
 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

Usage: perm_given_index(['a','b','c'], 3)

This uses the Lehmer code for the permutation as the values of j match that.

• lukmdo: This may be very nice i.e. for compression if you need to store a lot of permutations to use integer representation instead. Got inspired to write gist.github.com/lukmdo/7049748
• Thomas Kimber: Lehmer coding (and decoding) deserves to be ensconced somewhere within core python - at the very least, as a part of itertools. Anything where working with permutations is common needs a way to translate to and from the associated Lehmer index.

Answer 5

You can try implementing the random_permutation itertools recipes. For convenience I use a third-party library, more_itertools, that implements this recipe for us:

import more_itertools as mit
iterable = range(27)
mit.random_permutation(iterable)
# (24, 3, 18, 21, 17, 22, 14, 15, 20, 8, 4, 7, 13, 6, 25, 5, 12, 1, 9, 19, 23, 11, 16, 0, 26, 2, 10)

A random permutation is created for every call of the function. We can make a generator that yields these results for n calls. We will implement this generator and demonstrate random results with an abridged example:

def random_permute_generator(iterable, n=10):
 """Yield a random permuation of an iterable n times."""
 for _ in range(n):
 yield mit.random_permutation(iterable)
list(random_permute_generator(range(10), n=20))
# [(2, 7, 9, 6, 5, 0, 1, 3, 4, 8),
# (7, 3, 8, 1, 2, 6, 4, 5, 9, 0),
# (2, 3, 1, 8, 7, 4, 9, 0, 6, 5),
# (0, 5, 6, 8, 2, 3, 1, 9, 4, 7),
# (0, 8, 1, 9, 4, 5, 7, 2, 3, 6),
# (7, 2, 5, 8, 3, 4, 1, 0, 9, 6),
# (9, 1, 4, 5, 8, 0, 6, 2, 7, 3),
# (3, 6, 0, 2, 9, 7, 1, 4, 5, 8),
# (8, 4, 0, 2, 7, 5, 6, 1, 9, 3),
# (4, 9, 0, 5, 7, 1, 8, 3, 6, 2)
# ...]

For your specific problem, substitute the iterable and number of calls n with the appropriate values, e.g. random_permute_generator(iterable, n=5000).

See also more_itertools docs for further information on this tool.

---

Details

For those interested, here is the actual recipe.

From the itertools recipes:

def random_permutation(iterable, r=None):
 "Random selection from itertools.permutations(iterable, r)"
 pool = tuple(iterable)
 r = len(pool) if r is None else r
 return tuple(random.sample(pool, r))

Answer 6

You may want the itertools.permutations() function. Gotta love that itertools module!

NOTE: New in 2.6

• Mark Byers: This will be too slow - he said he has 27 elements.