[Solved] Fastest possible generation of permutation with defined element values in Python

Question

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.

Accepted Answer

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.