自然数を分割する方法を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]]