Random Sample Of N Distinct Permutations Of A List

05 January 2019 - 1 answer

Suppose I have a Python list of arbitrary length `k`. Now, suppose I would like a random sample of `n` , (where n <= k!) distinct permutations of that list. I was tempted to try:

``````import random
import itertools

k = 6
n = 10

mylist = list(range(0, k))

j = random.sample(list(itertools.permutations(mylist)), n)

for i in j:
print(i)
``````

But, naturally, this code becomes unusably slow when `k` gets too large. Given that the number of permutations that I may be looking for `n` is going to be relatively small compared to the total number of permutations, computing all of the permutations is unnecessary. Yet it's important that none of the permutations in the final list are duplicates.

How would you achieve this more efficiently? Remember, `mylist` could be a list of anything, I just used `list(range(0, k))` for simplicity.

Naïve implementation

Bellow the naïve implementation I did (well implemented by @Tomothy32, pure PSL using generator):

``````import numpy as np

mylist = np.array(mylist)
perms = set()
for i in range(n):                          # (1) Draw N samples from permutations Universe U (#U = k!)
while True:                             # (2) Endless loop
perm = np.random.permutation(k)     # (3) Generate a random permutation form U
key = tuple(perm)
if key not in perms:                # (4) Check if permutation already has been drawn (hash table)
perms.update(key)               # (5) Insert into set
break                           # (6) Break the endless loop
print(i, mylist[perm])
``````

It relies on `numpy.random.permutation` which randomly permute a sequence.

The key idea is:

• to generate a new random permutation (index randomly permuted);
• to check if permutation already exists and store it (as `tuple` of `int` because it must hash) to prevent duplicates;
• Then to permute the original list using the index permutation.

This naïve version does not directly suffer to factorial complexity `O(k!)` of `itertools.permutations` function which does generate all `k!` permutations before sampling from it.

There is something interesting about the algorithm design and complexity...

If we want to be sure that the loop could end, we must enforce `N <= k!`, but it is not guaranteed. Furthermore, assessing the complexity requires to know how many time the endless-loop will actually loop before a new random tuple is found and break it.

Limitation

Let's encapsulate the function written by @Tomothy32:

``````import math
def get_perms(seq, N=10):
rand_perms = perm_generator(mylist)
return [next(rand_perms) for _ in range(N)]
``````

For instance, this call work for very small `k<7`:

``````get_perms(list(range(k)), math.factorial(k))
``````

But will fail before `O(k!)` complexity (time and memory) when `k` grows because it boils down to randomly find a unique missing key when all other `k!-1` keys have been found.

Always look on the bright side...

On the other hand, it seems the method can generate a reasonable amount of permuted tuples in a reasonable amount of time when `N<<<k!`. Example, it is possible to draw more than `N=5000` tuples of length `k` where `10 < k < 1000` in less than one second.

When `k` and `N` are kept small and `N<<<k!`, then the algorithm seems to have a complexity:

• Constant versus `k`;
• Linear versus `N`.

This is somehow valuable.