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?

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.