我要在 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

您想要 itertools 图书馆的 combinations_with_replacement。代码如下所示：

from itertools import combinations_with_replacement
values = [i for i in range(1, 26)]
candidates = []
for tuple5 in combinations_with_replacement(values, 5):
    if sum(tuple5) == 100:
        candidates.append(tuple5)

我在这个问题上得到了 376 个候选人。正如上面评论中提到的，如果对 5 对的每个排列都计算一次，那么你会想看看，5 candidates-which 的排列可能并不完全不同。例如，无论您如何排列索引，(20,20,20,20,20) 都是相同的。然而，(21,20,20,20,19) 是 not-this 有一些不同的安排。

Answer 2

我认为 this 可能是您要搜索的内容：给定目标编号 SUM、左阈值 L、右阈值 R 和大小 K，找到 L 和 R 之间所有可能的 K 元素列表，总和为 SUM。尽管我能找到这个问题，但没有具体的名称。

Answer 3

Numpy 的另一种方法：

#!/usr/bin/env python

import numpy as np

start = 1
end = 25
entries = 5
total = 100

a = np.arange(start, end + 1)
c = np.array(np.meshgrid(a, a, a, a, a)).T.reshape(-1, entries)
assert(len(c) == pow(end, entries))
s = c.sum(axis=1)

#
# filter all combinations for those that meet sum criterion
#

valid_combinations = c[np.where(s == total)]
print(len(valid_combinations))   # 23746

#
# filter those combinations for unique permutations
#

unique_permutations = set(tuple(sorted(x)) for x in valid_combinations)
print(len(unique_permutations))  # 376

Answer 4

这是一个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 的回答一致。

我要在 python 中解决的数学程序是什么？

What is the math program I'm trying to solve in python?

python

math