Find all permutations of a string in Python

A permutation is one possible order of a set of items. The letters of "ABC" can be arranged in 6 orders. A string of n different letters has n! permutations (n × (n - 1) × ... × 1).

The program

def permutations(text):
    if len(text) <= 1:
        return [text]
    result = []
    for i, letter in enumerate(text):
        rest = text[:i] + text[i + 1:]
        for perm in permutations(rest):
            result.append(letter + perm)
    return result


print(permutations("ABC"))
print(len(permutations("ABCD")))

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
24

How it works

The function uses recursion:

• A string of 0 or 1 letters has only one order: itself.
• For a longer string, each letter takes a turn being the first letter. rest is the string without that letter.
• permutations(rest) gives every order of the remaining letters, and the first letter goes in front of each one.

For "ABC": A in front of "BC" and "CB", then B in front of "AC" and "CA", then C in front of "AB" and "BA".

The number of permutations grows very fast: 10 letters already give 3,628,800. Do not try to build the full list for long strings.

Another way: itertools.permutations

The standard library has this built in. It gives tuples of letters, so "".join() turns each one into a string. If letters repeat, as in "AAB", some orders are the same, and a set removes the copies:

from itertools import permutations

print(["".join(p) for p in permutations("ABC")])

all_orders = ["".join(p) for p in permutations("AAB")]
print(all_orders)
print(sorted(set(all_orders)))

['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
['AAB', 'ABA', 'AAB', 'ABA', 'BAA', 'BAA']
['AAB', 'ABA', 'BAA']

permutations("ABC", 2) gives orders of only 2 letters at a time, such as ('A', 'B').