Partition Problem

[Emile van Sebille]

Borrowing Tim's klistcombs:

def klistcombs(s, k):
    """Returns list of combinations of S taken K at a time.

    S must be a list.
    K must be >= 0.
    If K > len(S), an empty list is returned.
    Else if K is 0, a singleton list containing an empty list
    is returned.
    The k-combinations are returned in lexicographic order
    of their indices.
"""
    if k < 0:
        raise ValueError, "arg k == %d not >= 0" % k
    if len(s) < k:
        return []
    if k == 0:
        return [[]]

    answer = []
    indices = range(k)
    indices[-1] = indices[-1] - 1
    while 1:
        limit = len(s) - 1
        i = k - 1
        while i >= 0 and indices[i] == limit:
            i = i - 1
            limit = limit - 1
        if i < 0:
            break
        val = indices[i]
        for i in xrange( i, k ):
            val = val + 1
            indices[i] = val
        temp = []
        for i in indices:
            temp.append( s[i] )
        answer.append( temp )

    return answer        

def Partition(n,k):
    res=[[0]*k]                           
    res[0][0]=(n-k+1)                     
    for x in range(1,k):
        res[0][x]=1
    current = res[0][:]
    for i,j in klistcombs(range(k),2):
        while current[i] > current[j]+1:
            current[i] -= 1
            current[j] += 1
            res.append(current[:])
    return res

for i in Partition(9,3):
    print '\n\n',i

HTH,

-- 

Emile van Sebille
emile at fenx.com