Permutations

Why it costs this much

There are n! orderings, and building each one takes O(n).

Code

def permutations(items):
    if not items:
        return [[]]
    return [[x] + p
            for i, x in enumerate(items)
            for p in permutations(items[:i] + items[i+1:])]   # n! results of length n

Common pitfalls

n! grows fast: 10! is about 3.6 million and 15! is over a trillion. Duplicate values in the input need extra handling to avoid repeated results.