Generating All Permutations

Pick each element in turn as the first element of the permutation, and recursively generate the permutations of the remaining elements. The base case is a list of zero or one element, which has exactly one permutation, itself.

def permutations(values):
    if len(values) <= 1:
        return [list(values)]
    result = []
    for index, value in enumerate(values):
        rest = values[:index] + values[index + 1:]
        for tail in permutations(rest):
            result.append([value] + tail)
    return result


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

The output is six orderings: 1, 2, 3 then 1, 3, 2 then 2, 1, 3 then 2, 3, 1 then 3, 1, 2 then 3, 2, 1.

The mechanism is that a permutation is uniquely determined by its first element and a permutation of the rest. Because the base case has exactly one answer, and every larger list delegates to strictly smaller lists, the recursion is well founded and returns every ordering exactly once, with no duplicates and nothing missed.

The trade-off to name is factorial growth. Three elements give six permutations, ten elements give more than three million, and fifteen elements give more than a trillion, so the output size becomes the binding constraint long before the CPU does. There are two consequences worth stating. First, materialising the whole list of permutations is impossible for anything but a small input, so a generator that yields one at a time is the right shape. Second, the slicing on every level copies the list, so the time is not simply factorial but factorial times n, and a version that swaps elements in place avoids the copying.

The itertools module provides a permutations function that takes an iterable and returns an iterator over every ordering of it. Because it yields lazily, you can work through huge numbers of permutations without holding them all in memory.

from itertools import permutations

for order in permutations("ab"):
    print("".join(order))

The output is ab followed by ba, which are the two orderings of a two-character string. With three characters you would get six, and with ten you would get more than three million, produced one at a time.

The mechanism is that the helper keeps a tuple of the input elements and swaps them in place as it advances, recording a copy of the tuple each time it reaches a new arrangement. Because it hands back an iterator, the memory cost is one tuple at a time rather than the whole collection of results.

The trade-off to name is that using the library version is the right answer when the interviewer allows it, because it is faster than anything you would write in Python and it is well tested. What the interviewer usually wants from you is the recursive version from the previous answer, written from scratch, so that they can see that you understand the structure. The best of both is to explain the recursion, then note that in production you would use the library version and that its lazy iteration also solves the memory problem that the recursive materialised version has.

Write the recursive version directly: choose an element to place first, recurse on the rest, and prepend it to each result that comes back.

def permutations(values):
    if len(values) <= 1:
        return [list(values)]
    result = []
    for index, value in enumerate(values):
        rest = values[:index] + values[index + 1:]
        for tail in permutations(rest):
            result.append([value] + tail)
    return result


print(len(permutations([1, 2, 3, 4])))
print(permutations([1, 2]))

The outputs are 24 and the two orderings 1, 2 and 2, 1. Four elements give four factorial permutations, which is twenty-four.

The mechanism is the same choose-first recursion as before, but written without any helper. On duplicates there is a subtlety: the naive version treats two equal elements as distinct because they sit at different positions, so a list containing two ones produces duplicate permutations. The standard fix is to skip an element when an identical one at an earlier position has already been considered in the same call, which requires either sorting first and comparing neighbours, or keeping a set of the values used in the current branch.

The trade-off to name is that the duplicate handling costs a set lookup or an extra comparison per element per level, and it is only worth paying when duplicates are actually possible. If the input is guaranteed to have distinct elements, the simpler version is better. Another trade-off is memory: this version materialises every permutation, which for ten elements means holding millions of lists at once, so a generator version that yields each result as it is produced is the one to use in a real program.