# Generating permutations

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?

• 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. Sep 1, 2016 at 8:49

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.