Python Program to Print All Permutations

Lists every ordering of a list's items by choosing an item for each place in turn, then undoing the choice to try the next one.

A permutation is one ordering of a set of items. The letters A, B and C can be ordered in 3 × 2 × 1 = 6 ways: ABC, ACB, BAC, BCA, CAB and CBA. Four items have 24 orderings, and n items have n! ("n factorial").

The program builds the orderings by backtracking: it chooses an item for the first place, then one of the items left for the next place, and so on. When the ordering is full it saves it, then undoes the last choice and tries the next item in that place. Choose, explore, undo: that pattern is behind every backtracking program.

Program

def permutations(items):
    """Every ordering of items, as a list of lists."""
    result = []
    current = []
    used = [False] * len(items)

    def backtrack():
        if len(current) == len(items):
            result.append(current.copy())
            return
        for i, item in enumerate(items):
            if not used[i]:
                used[i] = True        # choose this item
                current.append(item)
                backtrack()           # fill the places after it
                current.pop()         # undo the choice
                used[i] = False

    backtrack()
    return result


for ordering in permutations(["A", "B", "C"]):
    print("".join(ordering))

Open in the editor Download permutations.py

Output

ABC
ACB
BAC
BCA
CAB
CBA

How it works

Visualize Step through the program line by line: each step below shows up as its line runs.

1. result collects the finished orderings. current is the ordering being built, and used[i] says whether items[i] is already in it.
2. backtrack is a function inside permutations, so it can use those three lists (scope). When current holds every item, it's a complete ordering: a copy goes into result, because current itself will keep changing.
3. Otherwise, each item that isn't used yet is tried in the next place: it's marked as used and added to the end of current. That's the choice.
4. backtrack() calls itself to fill the places after it, finding every ordering that starts this way.
5. Back from that call, the choice is undone: the item comes off the end of current and is free again, so the loop can try the next item in the same place.
6. The first call starts with an empty ordering. When it returns, every ordering is in result.
7. The program prints each ordering of A, B and C, joining its letters into one word.

How current grows and shrinks while the orderings that start with A are found:

Time and space complexity

There are n! orderings, and each one is copied into result in n steps, so the time is O(n × n!). Factorials grow fast: 3 items have 6 orderings, 10 items have 3,628,800, so listing every ordering only works for short lists. Besides the result, the function keeps current and used, n items each, and the calls to backtrack go n deep, so the extra space is O(n). The result itself holds n × n! items: for 10 items, over 36 million.

Other ways to write it

With itertools.permutations()

The standard library makes the orderings for you, as tuples, in the same order. It's the one to use in real programs, and it can also pick orderings of only some of the items (modules).

from itertools import permutations

print(["".join(p) for p in permutations("ABC")])
pairs = list(permutations("ABCD", 2))
print(len(pairs), "ways to pick 2 of 4 in order")

By swapping items in place

This version needs no used list: it swaps each item into the next place, explores, then swaps it back. The orderings come out in a slightly different order: CBA before CAB.

def permute(items, start=0):
    if start == len(items):
        print("".join(items))
        return
    for i in range(start, len(items)):
        items[start], items[i] = items[i], items[start]  # choose
        permute(items, start + 1)                        # explore
        items[start], items[i] = items[i], items[start]  # undo

permute(["A", "B", "C"])

Try it yourself

• Add a fourth letter, and print len() of the result to check there are 24 orderings.
• Pass a word as a string, such as permutations("CAT"): a string can be looped over like a list.
• Try ["A", "A", "B"]: each ordering appears twice, as the function can't tell the two As apart. Keep one of each with a set of the joined words.
• Save current once it holds 2 items instead of all of them, to list the ways to pick 2 of the 3 letters in order.

More backtracking programs

• Python Program to Find All Subsets of a Set Intermediate
• Python Program to Solve the N-Queens Problem Advanced