返回一个可变长度的序列，其总和等于给定整数

Question

采用 f(x,y,z) 形式，其中 x 是给定的整数和，y 是序列的最小长度，并且z 是序列的最大长度。但现在让我们假设我们正在处理一个固定长度的序列，因为否则我将花费很长时间来写这个问题。

所以我们的函数是 f(x,r) ，其中 x 是给定的整数和，r 是列表中序列的长度可能的序列。

对于 x = 10 和 r = 2，这些是可能的组合：

1 + 9
2 + 8
3 + 7
4 + 6
5 + 5

让我们将其存储在 Python 中作为对列表：

[(1,9), (2,8), (3,7), (4,6), (5,5)]

因此用法如下：

>>> f(10,2)
[(1,9), (2,8), (3,7), (4,6), (5,5)]

回到原始状态问题，其中为 (y,x) 范围内的每个长度返回一个序列。我采用前面定义的 f(x,y,z) 形式，并省略了长度为 1 的序列（其中 yz == 0） ，这看起来像：

>>> f(10,1,3)
[{1: [(1,9), (2,8), (3,7), (4,6), (5,5)],
  2: [(1,1,8), (1,2,7), (1,3,6) ... (2,4,4) ...],
  3: [(1,1,1,7) ...]}]

所以输出是一个字典列表，其中值是一个对列表。并不完全是最佳的。

所以我的问题是：

1. 是否有一个库可以处理这个问题？
2. 如果没有，有人可以帮我编写我提到的两个函数吗？ （首先固定序列长度）？
3. 由于我对相当琐碎的数学知识的巨大差距，您能否忽略我的整数存储方法并使用最有意义的结构？

对今天所有这些算术问题感到抱歉。谢谢！

Answer 1

当我们处理预突变时， itertools 模块肯定会很有帮助 - 然而，这看起来可疑地像一个家庭作业...

编辑：不过看起来很有趣，所以我会尝试一下。

编辑2：这就是你想要的吗？

from itertools import combinations_with_replacement
from pprint import pprint

f = lambda target_sum, length: [sequence for sequence in combinations_with_replacement(range(1, target_sum+1), length) if sum(sequence) == target_sum]

def f2(target_sum, min_length, max_length):
    sequences = {}
    for length in range(min_length, max_length + 1):
        sequence = f(target_sum, length)
        if len(sequence):
            sequences[length] = sequence
    return sequences

if __name__ == "__main__":
    print("f(10,2):")
    print(f(10,2))
    print()
    print("f(10,1,3)")
    pprint(f2(10,1,3))

输出：

f(10,2):
[(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)]

f(10,1,3)
{1: [(10,)],
 2: [(1, 9), (2, 8), (3, 7), (4, 6), (5, 5)],
 3: [(1, 1, 8),
     (1, 2, 7),
     (1, 3, 6),
     (1, 4, 5),
     (2, 2, 6),
     (2, 3, 5),
     (2, 4, 4),
     (3, 3, 4)]}

Answer 2

该问题称为整数分区，并且具有被广泛研究。

在这里您可以找到论文比较了几种算法的性能（并提出了一种特定的算法），但网络上有很多参考文献。

Answer 3

我刚刚编写了一个递归生成器函数，您应该弄清楚如何自己从中获取列表...

def f(x,y):
    if y == 1:
        yield (x, )
    elif y > 1:
        for head in range(1, x-y+2):
            for tail in f(x-head, y-1):
                yield tuple([head] + list(tail))

def f2(x,y,z):
    for u in range(y, z+1):
        for v in f(x, u):
            yield v

编辑：我只是看到它并不完全是您想要的，我的版本也会生成重复项，其中只有顺序不同。但是您可以通过对所有结果进行排序并检查重复的元组来简单地过滤掉它们。