These functions produce integer partitions in reverse lexicographic and lexicographic order respectively.

def revlex_partitions(n): """ Generate all integer partitions of n in reverse lexicographic order """ if n == 0: yield [] return for p in revlex_partitions(n - 1): if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]): p[-1] += 1 yield p p[-1] -= 1 p.append(1) yield p p.pop() def lex_partitions(n): """ Generate all integer partitions of n in lexicographic order """ if n == 0: yield [] return for p in lex_partitions(n - 1): p.append(1) yield p p.pop() if len(p) == 1 or (len(p) > 1 and p[-1] < p[-2]): p[-1] += 1 yield p p[-1] -= 1

Example program:

def main(): for p in revlex_partitions(5): print(p) print() for p in lex_partitions(5): print(p) if __name__ == '__main__': main()

Output:

[5] [4, 1] [3, 2] [3, 1, 1] [2, 2, 1] [2, 1, 1, 1] [1, 1, 1, 1, 1] [1, 1, 1, 1, 1] [2, 1, 1, 1] [2, 2, 1] [3, 1, 1] [3, 2] [4, 1] [5]

Reference: David Eppstein, IntegerPartitions.py