A generalization of Bézier surfaces, called the S-patch, uses an interesting scheme for indexing its control points.

In the case of an n-sided surface of degree d, each index has n non-negative integers that sum to d, and all possible configurations are used.

For example, for a 3-sided quadratic (degree 2) surface the control points are:

> indices 3 2 => [[0,0,2],[0,1,1],[0,2,0],[1,0,1],[1,1,0],[2,0,0]]

Given the degree and the number of sides, generate all control point indices.
The order of the indices in the list can be arbitrary, so for the above example

> [[1,1,0],[2,0,0],[0,0,2],[0,2,0],[0,1,1],[1,0,1]]

is also a good solution.

Difficulty: introductory

Starter code:

def indices(n, d):
	

Solutions:
def gen(n, d):
    if d == 0 or n == 1:
        yield [d]*n
    else:
        for x in range(d+1):
            for y in gen(n-1, d-x):
                yield [x] + y

def indices(n, d):
    return list(gen(n, d))

import itertools
def indices(n, d):
    return list(recurse(n,d, []))

def recurse(n, d, prefix):
    if n == 0:
        return prefix
    if n == 1:
        return [prefix + [d]]
    res = []
    for i in range(d+1):
        res += recurse(n-1, d-i, prefix + [i])
    return res



def indices(n, d):
    return [[r] + point for r in range(d + 1)
                        for point in indices(n-1, d-r)] if n > 1 else [[d]]


import itertools 

dic={1:[[1]],2:[[2],[1,1]],3:[[3],[2,1],[1,1,1]],
    4:[[4],[3,1],[2,1,1],[2,2],[1,1,1,1]],
    5:[[5],[4,1],[3,1,1],[3,2],[2,1,1,1],[2,2,1],[1,1,1,1,1]],
    6:[[6],[5,1],[4,1,1],[4,2],[3,1,1,1],[3,2,1],[3,3],[2,1,1,1,1],[2,2,1,1],[2,2,2],[1,1,1,1,1,1]],
    7:[[7],[6,1],[5,1,1],[5,2],[4,1,1,1],[4,2,1],[4,3],[3,1,1,1,1],[3,2,1,1],[3,2,2],[3,3,1],[2,1,1,1,1,1],[2,2,1,1,1],[2,2,2,1],[1,1,1,1,1,1,1]],
    8:[[8],[7,1],[6,1,1],[6,2],[5,1,1,1],[5,2,1],[5,3],[4,1,1,1,1],[4,2,1,1],[4,2,2],[4,3,1],[4,4],[3,1,1,1,1,1],[3,2,1,1,1],[3,2,2,1],[3,3,1,1],[2, 3, 3],[2,1,1,1,1,1,1],[2,2,1,1,1,1],[2,2,2,1,1],[2,2,2,2],[1,1,1,1,1,1,1,1]],
    9:[[9],[8,1],[7,1,1],[7,2],[6,1,1,1],[6,2,1],[6,3],[5,1,1,1,1],[5,2,1,1],[5,2,2],[5,3,1],[5,4],[4,3,1, 1],[4,1,1,1,1,1],[4,2,1,1,1],[4,2,2,1],[4,2,3],[3,3,3],[3,3,1,1,1],[3,3,2,1],[3,1,1,1,1,1,1],[3,2,1,1,1,1],[3,2,2,1,1],[3,2,2,2],[4,4,1],[2,1,1,1,1,1,1,1],[2,2,1,1,1,1,1],[2,2,2,1,1,1],[2,2,2,2,1],[1,1,1,1,1,1,1,1,1]],
        
    }


def indices(n, d):
    print (n,d)
    l=[]
    original=[0]*n
    if not d:
        return [original]

    for i in dic[d]:
        if len(i)>n:
            continue
        t=i+[0]*(n-len(i))
        l.extend(list(set(list(itertools.permutations(t)  )  )))
    print("c->",sorted(l)  )
    
    
    

    return map(list,l)

def indices(n, d):
    result=[]
    temp=[]
    def tt (n, d,temp):
        if d==1:
            result.extend([temp+[n]])
            return 0
        for i in range(0,n+1):
            aa=temp+[i]
            tt(n-i, d-1,aa)
    tt(d, n,temp)
    return result

def indices(n, d):
    if n == 1: return [[d]]
    if d == 0: return [[0 for i in range(n)]]
    sols = []
    for i in range(d+1):
        sols += [subsol + [i] for subsol in indices(n-1,d-i)]
    
    return sols
    raise NotImplementedError('todo')

def indices(n, d):

    result = ([i] for i in range(d + 1))  # start with all possible lists of length 1 with sum within limit

    # until have lists of len n: add every possible num to each list in result that doesn't put over limit d
    for iteration in range(n - 1):
        result = (i + [j] for i in result for j in range(d + 1) if sum(i) + j <= d)

    return list(filter(lambda r: sum(r) == d, result))  # return combinations with sum d

def indices(n, d):
    if n == 1:
        return [[d]]
    result = []
    for i in range(d+1):
        for x in indices(n-1, d-i):
            result.append([i] + x)
    return result


def indices(n, d):
    if d<0:
        return []
    elif n==1:
        return [[d]]
    elif n==2:
        return [[i,d-i] for i in range(d+1)]
    else:
        return [[i]+p for i in range(d+1) for p in indices(n-1,d-i)]

def indices(n, d):
    from itertools import combinations_with_replacement
    
    lst = []
    for c in combinations_with_replacement(range(n), d):
        base = [0]*n
        for i in c:
            base[i] += 1
        lst.append(base)
    return lst