generating partitions

parts.py

# Generator for partitions of an integer.
#
# See http://jeromekelleher.net/category/combinatorics.html

def ruleAsc(n):
    a = [0 for i in range(n + 1)]
    k = 1
    a[1] = n
    while k != 0:
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

# yield partitions of n whose sizes are all >= m
def ruleAsc2(n,m):
    a = [m-1 for i in range(n + 1)]
    k = 1
    a[1] = n-(m-1)
    while k != 0:
        # invariants:
        #   a[0] + a[1] + ... + a[k] == n
        #   a[0] <= a[1] <= ... <= a[k]
        x = a[k - 1] + 1
        y = a[k] - 1
        k -= 1
        while x <= y:
            a[k] = x
            y -= x
            k += 1
        a[k] = x + y
        yield a[:k + 1]

def test1():
  for p in ruleAsc2(15,1): print p

for p in ruleAsc2(15,2): print p