Python code for generating integer compositions. First algorithm thanks to Knuth 7.2.1.3

gistfile1.py

def compositions(t=2,s=2):
    """knuth 7.2.1.3"""
    q = [0] * (t+1)
    r = None
    q[0] = s
    while True:
        yield q[:]
        if q[0] == 0:
            if r==t:
                break
            else:
                q[0] = q[r] - 1
                q[r] = 0
                r = r + 1
        else:
            q[0] = q[0] - 1
            r = 1
        q[r] = q[r] + 1
        



def compositions2(t,s):
    """break integer s into t+1 parts"""
    for x in comp(t,s,[0]*(t+1),0):
        yield x
    
def comp(t,s,q,i=0):
    if i == t:
        q[i] = s
        yield q[:]
    else:
        for x in range(s,-1,-1):
            q[i] = x
            for y in comp(t,s-x,q,i+1):
                yield y



def compositions3(t,s):
    """faster, uses copy semantics"""
    for x in comp3(t,s,[0]*(t+1),0):
        yield x
    
def comp3(t,s,q,i=0):
    if i == t:
        q[i] = s
        yield q
    elif s == 0:
        yield q
    else:
        for x in range(s,-1,-1):
            u = q[:]
            u[i] = x
            for y in comp3(t,s-x,u,i+1):
                yield y            

for x in compositions3(4,2):
    print x