自然数を分割する方法をpythonで列挙する

分割数の求め方。

def partitions(n):
    if n == 0:
        yield []
        return

    for p in partitions(n-1):
        yield [1] + p
        if len(p) == 1 or (len(p) > 1 and p[0] < p[1]):
            yield [p[0] + 1] + p[1:]


print(list(partitions(1))) # => [[1]]
print(list(partitions(2))) # => [[1, 1], [2]]
print(list(partitions(3))) # => [[1, 1, 1], [1, 2], [3]]
print(list(partitions(4))) # => [[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]]
print(list(partitions(5))) # => [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]]

参考

code.activestate.com