Python problem 29 of 30

Permutations by hand

Python
Hard

Write permutations(items) that returns every ordering of a list of distinct items, without using itertools.

permutations([1, 2, 3])
# [[1, 2, 3], [1, 3, 2], [2, 1, 3],
#  [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Show hint

Choose which item goes first. The rest of the answer is every permutation of the remaining items.

Show solution

def permutations(items):
    if len(items) <= 1:
        return [list(items)]
    out = []
    for i, first in enumerate(items):
        rest = items[:i] + items[i + 1:]
        for perm in permutations(rest):
            out.append([first] + perm)
    return out

The base case is a list of zero or one items, which has exactly one ordering. Each level of recursion fixes one position. There are n! permutations (6 for 3 items, over 3.6 million for 10), so this grows even faster than the 2ⁿ subsets problem.

Want a problem like this every day? See today's problem and keep a streak going.