python - 我想用 python 解决的数学程序是什么？

Question

我正在尝试用 python 解决这个数学问题，但我不确定它叫什么:

• 答案 X 总是 100
• 给定一个包含 5 个整数的列表，它们的和等于 X
• 每个整数必须介于 1 到 25 之间
• 整数可以在列表中出现一次或多次

我想找到匹配的 5 个整数的所有可能的唯一列表。

这些将匹配:

• 20,20,20,20,20
• 25,25,25,20,5
• 10,25,19,21,25

还有更多。

我查看了 itertools.permutations，但我认为它无法处理列表中的重复整数。我想这一定有一个标准的数学算法，但我的搜索查询一定很差。

唯一要提及的是，列表大小是否可以从 10 个整数更改为其他长度(6、24 等)是否重要。

Answer 1

这是一个 constraint satisfaction problem .这些通常可以通过一种称为线性规划的方法来解决:您修复解决方案的一部分，然后解决剩余的子问题。在 Python 中，我们可以使用递归函数来实现这种方法:

def csp_solutions(target_sum, n, i_min=1, i_max=25):
    domain = range(i_min, i_max + 1)
    if n == 1:
        if target_sum in domain:
            return [[target_sum]]
        else:
            return []
    solutions = []
    for i in domain:
        # Check if a solution is still possible when i is picked:
        if (n - 1) * i_min <= target_sum - i <= (n - 1) * i_max:
            # Construct solutions recursively:
            solutions.extend([[i] + sol 
                              for sol in csp_solutions(target_sum - i, n - 1)])
    return solutions


all_solutions = csp_solutions(100, 5)

这产生了 23746 个解决方案，与 Alex Reynolds 的回答一致。