给定整数n，则返回给定长度M的所有组合m，其中m_1+m_2+m_3+.....m_m =n

Question

我试图解决一个老问题，但我找不到一个算法(我觉得它是递归的)或理想的迭代工具解决方案。

给定整数n，则返回给定长度M的所有组合m，其中m_1+m_2+m_3+.....m_m =n

例如:如果n=2καιM=3，我需要得到列表m: 2，0，0，0，0，0，2，1，1，1，1，0，1，1，1，但对于任意n和M。

Answer 1

您是对的，这是一个递归的解决方案。实际上，假设我们希望f(n,M)返回一个与n相加的M元素的元组列表。应该不难说服自己，对于任何非负的k<=n，f(n-k,M-1)中的每个元组都可以通过简单地添加一个k项从f(n,M)转换为元组(反之亦然，如果去掉这个术语，f(n,M)中的每个元组都会从f(n-k,M-1)中产生一个元组)。考虑到这一点：

def f(n,M):
    if M==1:
        return [(n,)]
    sequences = []
    for k in range(n+1):
        for sequence in f(n-k,M-1):
            sequences.append((k,)+sequence)
    return sequences

注意这里的基本情况--如果是M==1，则只有一个可能的序列。您还可能想要处理M==0，如果n==0和[]不是这样的话，它应该返回n==0。

最好是作为生成器这样做，因为您可以动态地生成这些序列：

def f(n,M):
    if M==1:
        yield [(n,)]
    else:
        for k in range(n+1):
            yield from map(lambda sequence: (k,)+sequence, f(n-k, M-1))

我不相信迭代工具可以以任何明显的方式帮助实现这一点-- combinations当然可以帮助生成所有可能的M-tuples，因此我们以后只能将那些加在一起的东西保持为n，但是很快就会变得非常慢。直接生成有效的元组需要在创建这些元组时对所发生的“算术”有一定的了解，据我所知，这不是迭代工具所要做的事情。