def partitions2(n):
    """
    Generates all partitions of {1,...,n}.

    For n=12, this finishes in 4.48 seconds.

    """
    if n == 0:
        yield [[]]
    elif n == 1:
        yield [[0]]
    else:
        a = [0] * (n + 1)
        b = [1] * n
        m = 1
        while True:
            yield a[1:]
            if a[n] == m:
                j = n - 1
                while a[j] == b[j]:
                    j -= 1
                if j == 1:
                    break
                else:
                    a[j] += 1
                m = b[j]
                if a[j] == b[j]:
                    m += 1
                j += 1
                while j < n:
                    a[j] = 0
                    b[j] = m
                    j += 1
                a[n] = 0
            else:
                a[n] += 1
