3
\$\begingroup\$

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?

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Sep 1 '16 at 8:49
5
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.