Fastest possible generation of permutation with defined element values in Python

Question

Trying to generate permutations, could be used with generator or produced List of Lists (but maybe I need a lot of memory?) Looked on the Internet and SO, but couldn't find a version where I define the values for each element.

BTW How many permutations it will be?

8 elements with each value from 1-15

Here is my code, but maybe there is a better, faster way to generate it:

Any tips are appreciated!

import time
from tqdm import tqdm
def permutations(iterable, r=None):
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = range(n)
    cycles = range(n, n-r, -1)
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

plist = []

for item in tqdm(permutations('123456789ABCDEF',8)):
  plist.append(item)


len(plist)

Answer 1

You just copied the code from the itertools.permutations() documentation. That explicitly states that it is roughly equivalent, because it is only there to help you understand what itertools.permutations() does. The code is not intended to be used in production settings.

Use itertools.permutations() itself. The itertools module is designed for maximum efficiency already. The module is coded in C, and will always beat a pure Python implementation, hands down.

You are also wasting iterations on appending values to a list; each .append() expression requires an attribute lookup and a method call. You can build plist in a single expression by calling list():

plist = list(permutations('123456789ABCDEF', 8))

However, you really don't want to execute that call, because that'll take a lot of time to produce all possible permutations as separate objects, and allocating the memory for that takes time and will slow down your machine.

The number of k-permutations of n is calculated with k! / (n - k)!), with n=15 and k=8, that's 15! / (15 - 8)!, so just over a quarter billion results, 259_459_200. On a 64-bit OS that'll require about ~30GB of memory (2GB for the list object, 27G for the tuples, mere bytes for the 15 1-digit strings as they are shared).

If you really want to process those permutations, I'd just loop over the generator and use each result directly. You'll still have to iterate a quarter-billion times, so it'll still take a lot of time, but at least you don't then try to hold it all in memory at once.

Alternatively, always look for other ways to solve your problem. Generating all possible permutations will produce a very large number of possibilities. Your previous question received an answer that pointed out that for than specific problem, searching through 200kb of data for likely candidates was more efficient than to do 40k searches for every possible 8-permutation of 8. With 259 million permutations there is an even larger chance that processing your problem from another direction might keep your problem space manageable.