Generating permutations

Question

I have an algorithm for generating permutations in Python

from collections import Counter
def permutations(A):
 def permutations(A):
 if len(A) == 0:
 return
 if len(A) == 1:
 yield A
 else:
 for i in range(1, len(A)):
 for p in permutations(A[i:]): # Pretend slicing is O(1)
 for q in permutations(A[:i]): # Pretend slicing is O(1)
 yield p + q # Pretend O(1)
 yield q + p # Pretend O(1)
 return set(permutations(A))
P = permutations((1, 2, 3))
C = Counter(P)
print(P)
print(C)

Which has output

{(3, 1, 2), (1, 3, 2), (3, 2, 1), (2, 3, 1), (1, 2, 3), (2, 1, 3)}
Counter({(2, 1, 3): 1, (1, 3, 2): 1, (3, 1, 2): 1, (3, 2, 1): 1, (2, 3, 1): 1, (1, 2, 3): 1})

Assuming I don't care about the time it takes to slice/concatenate arrays, is this the most efficient algorithm for generating permutations? If not, what can I do to improve it?

• Peter Taylor: Rule of thumb: if you have to use set(...) to deduplicate any time of combinatorial object, you probably don't have the most efficient algorithm.

Answer 1

Well, the obvious method would be to use the itertools module which has exactly what you want. Here are the docs, just in case you'll need to look up for something else.

from itertools import permutations
def generate_permutations():
 return list(permutations([1,2,3]))

The above will return:

[(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

Below, you can find the algorith of this module:

def permutations(iterable, r=None):
 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

As you can see, this is using just a while loop do do what you did in 3 separate for loops. For this kind of operations, I strongly recommend using the itertools module.