Python - 如何对一列数字的所有组合求和以达到目标。号码的使用是可选的
Python - How to sum all combinations of a list of numbers in order to reach a goal. Use of number is optional
我有一个号码列表
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
我想以各种方式求和，以尝试达到目标数 8276。我还需要看看舍弃美分或四舍五入是否有助于达到目标。请注意，使用数字是可选的。
我试过了
from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1): #xrange will return the values 1,2,3,4 in this loop
if sum(list(combinations(lis, i))) == 8276:
print list(combinations(lis, i))
但这给了我
TypeError: unsupported operand type(s) for +: 'int' and 'tuple'
我不确定为什么或如何解决。
您试图对给定长度的所有组合求和，而不是计算单个组合的总和。相反，您应该遍历组合并检查每个组合的总和：
from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1):
for comb in combinations(lis, i):
if sum(comb) == 8276:
print comb
特定错误的原因是 sum 采用可选参数 start，这是默认值。如果未提供参数，则默认为 0。本质上，您的原始代码试图执行以下操作：
>>> sum([(1,), (2,)])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'tuple'
既然你提到了：
I also need to see whether throwing away the cents or rounding helps reaching the goal.
..下面的代码将显示最接近的 n 种组合，以及它们与目标数字的绝对差异。
适用于 python3 和 python2
from itertools import combinations
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
diffs = []
for n in range(1, len(lis)+1):
numbers = combinations(lis, n)
# list the combinations and their absolute difference to target
for combi in numbers:
diffs.append([combi, abs(target - sum(combi))])
diffs.sort(key=lambda x: x[1])
for item in diffs[:show]:
print(item[0], round(item[1],10))
输出将显示前 n 个最接近的组合（组合/与目标数字的绝对差值）：
(5084, 3298.85) 106.85
(10, 5084, 3298.85) 116.85
(5084, 156.43, 3298.85) 263.28
(10, 5084, 156.43, 3298.85) 273.28
(5084, 381.3, 3298.85) 488.15
这表明你能得到的最接近的是(5084, 3298.85)，显示相差106.85。
备注
顺便说一句 Note on floating point calculation:
编辑
为了好玩，上面脚本的浓缩版：
from itertools import combinations
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
diffs = [item for sublist in [[
[combi, abs(target - sum(combi))] for combi in combinations(lis, n)
] for n in range(1, len(lis)+1)] for item in sublist]
diffs.sort(key=lambda x: x[1])
[print(item[0], round(item[1],10)) for item in diffs[:show]]
如果您想考虑可以舍弃美分或四舍五入到最接近的整数的情况，这里有一个解决方案。这个需求把一个简单的解决方案变成了一个相当复杂的解决方案。为了考虑到上述要求，我扩展了每个数字以包括其他可能的情况。展开后的列表显示了获取组合的新列表：
import math
import itertools as it
tolerance = 150
target_sum = 8392
found = False
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
def add_throw_and_round(num):
num_list = [num]
if int(num) != float(num):
num_list.append(math.floor(num))
if round(num) not in num_list:
num_list.append(round(num))
return sorted(num_list)
lis_expanded = map(add_throw_and_round, lis)
print "Expanded list:\n", lis_expanded, "\n\nTarget sum:\n", target_sum, "\n"
for n in range(1,len(lis) + 1): # n is number of summands in pick
lis_combos = it.combinations(lis_expanded, n)
for lis_combo_n in lis_combos:
for combo_n in (it.product(*lis_combo_n)):
sum_ = sum(combo_n)
if sum_ == target_sum:
found = True
answer = combo_n
if sum_ > target_sum - tolerance and sum_ < target_sum + tolerance:
print "sum:", sum_, "\tCombination: ", combo_n
if found:
print "\nThere is a match: ", answer
else:
print "\nNo exact match found"
所以我决定显示所有在目标总和 150 以内的总和，只是为了看看它是否有效。如果总和正好是 8276，则没有匹配项：
>>>
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====
Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]]
Target sum:
8276
sum: 8382.0 Combination: (5084, 3298.0)
sum: 8382.85 Combination: (5084, 3298.85)
sum: 8383.0 Combination: (5084, 3299.0)
sum: 8392.0 Combination: (10, 5084, 3298.0)
sum: 8392.85 Combination: (10, 5084, 3298.85)
sum: 8393.0 Combination: (10, 5084, 3299.0)
No exact match found
>>>
注意上面它测试了美分被舍弃和四舍五入的情况。
只是为了测试当目标总和匹配时它是否会报告匹配，我尝试了 target_sum = 8392 因为输出显示一个组合应该匹配它。所以这里是这种情况下的输出：
>>>
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====
Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]]
Target sum:
8392
sum: 8382.0 Combination: (5084, 3298.0)
sum: 8382.85 Combination: (5084, 3298.85)
sum: 8383.0 Combination: (5084, 3299.0)
sum: 8392.0 Combination: (10, 5084, 3298.0)
sum: 8392.85 Combination: (10, 5084, 3298.85)
sum: 8393.0 Combination: (10, 5084, 3299.0)
sum: 8538.0 Combination: (5084, 156.0, 3298.0)
sum: 8538.85 Combination: (5084, 156.0, 3298.85)
sum: 8539.0 Combination: (5084, 156.0, 3299.0)
sum: 8538.43 Combination: (5084, 156.43, 3298.0)
sum: 8539.28 Combination: (5084, 156.43, 3298.85)
sum: 8539.43 Combination: (5084, 156.43, 3299.0)
There is a match: (10, 5084, 3298.0)
>>>
我有一个号码列表
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
我想以各种方式求和，以尝试达到目标数 8276。我还需要看看舍弃美分或四舍五入是否有助于达到目标。请注意，使用数字是可选的。
我试过了
from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1): #xrange will return the values 1,2,3,4 in this loop
if sum(list(combinations(lis, i))) == 8276:
print list(combinations(lis, i))
但这给了我
TypeError: unsupported operand type(s) for +: 'int' and 'tuple'
我不确定为什么或如何解决。
您试图对给定长度的所有组合求和，而不是计算单个组合的总和。相反，您应该遍历组合并检查每个组合的总和：
from itertools import combinations
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
for i in xrange(1, len(lis) + 1):
for comb in combinations(lis, i):
if sum(comb) == 8276:
print comb
特定错误的原因是 sum 采用可选参数 start，这是默认值。如果未提供参数，则默认为 0。本质上，您的原始代码试图执行以下操作：
>>> sum([(1,), (2,)])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'tuple'
既然你提到了：
I also need to see whether throwing away the cents or rounding helps reaching the goal.
..下面的代码将显示最接近的 n 种组合，以及它们与目标数字的绝对差异。
适用于 python3 和 python2
from itertools import combinations
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
diffs = []
for n in range(1, len(lis)+1):
numbers = combinations(lis, n)
# list the combinations and their absolute difference to target
for combi in numbers:
diffs.append([combi, abs(target - sum(combi))])
diffs.sort(key=lambda x: x[1])
for item in diffs[:show]:
print(item[0], round(item[1],10))
输出将显示前 n 个最接近的组合（组合/与目标数字的绝对差值）：
(5084, 3298.85) 106.85
(10, 5084, 3298.85) 116.85
(5084, 156.43, 3298.85) 263.28
(10, 5084, 156.43, 3298.85) 273.28
(5084, 381.3, 3298.85) 488.15
这表明你能得到的最接近的是(5084, 3298.85)，显示相差106.85。
备注
顺便说一句 Note on floating point calculation:
编辑
为了好玩，上面脚本的浓缩版：
from itertools import combinations
# set the number of closest combinations to show, the targeted number and the list
show = 5
target = 8276
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
diffs = [item for sublist in [[
[combi, abs(target - sum(combi))] for combi in combinations(lis, n)
] for n in range(1, len(lis)+1)] for item in sublist]
diffs.sort(key=lambda x: x[1])
[print(item[0], round(item[1],10)) for item in diffs[:show]]
如果您想考虑可以舍弃美分或四舍五入到最接近的整数的情况，这里有一个解决方案。这个需求把一个简单的解决方案变成了一个相当复杂的解决方案。为了考虑到上述要求，我扩展了每个数字以包括其他可能的情况。展开后的列表显示了获取组合的新列表：
import math
import itertools as it
tolerance = 150
target_sum = 8392
found = False
lis = [497.96, 10, 5084, 156.43, 381.3, 3298.85, 625.68]
def add_throw_and_round(num):
num_list = [num]
if int(num) != float(num):
num_list.append(math.floor(num))
if round(num) not in num_list:
num_list.append(round(num))
return sorted(num_list)
lis_expanded = map(add_throw_and_round, lis)
print "Expanded list:\n", lis_expanded, "\n\nTarget sum:\n", target_sum, "\n"
for n in range(1,len(lis) + 1): # n is number of summands in pick
lis_combos = it.combinations(lis_expanded, n)
for lis_combo_n in lis_combos:
for combo_n in (it.product(*lis_combo_n)):
sum_ = sum(combo_n)
if sum_ == target_sum:
found = True
answer = combo_n
if sum_ > target_sum - tolerance and sum_ < target_sum + tolerance:
print "sum:", sum_, "\tCombination: ", combo_n
if found:
print "\nThere is a match: ", answer
else:
print "\nNo exact match found"
所以我决定显示所有在目标总和 150 以内的总和，只是为了看看它是否有效。如果总和正好是 8276，则没有匹配项：
>>>
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====
Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]]
Target sum:
8276
sum: 8382.0 Combination: (5084, 3298.0)
sum: 8382.85 Combination: (5084, 3298.85)
sum: 8383.0 Combination: (5084, 3299.0)
sum: 8392.0 Combination: (10, 5084, 3298.0)
sum: 8392.85 Combination: (10, 5084, 3298.85)
sum: 8393.0 Combination: (10, 5084, 3299.0)
No exact match found
>>>
注意上面它测试了美分被舍弃和四舍五入的情况。 只是为了测试当目标总和匹配时它是否会报告匹配，我尝试了 target_sum = 8392 因为输出显示一个组合应该匹配它。所以这里是这种情况下的输出：
>>>
===== RESTART: C:/Users/Joe/Desktop/scripts/Stack_overflow/cents_py2.py =====
Expanded list:
[[497.0, 497.96, 498.0], [10], [5084], [156.0, 156.43], [381.0, 381.3], [3298.0, 3298.85, 3299.0], [625.0, 625.68, 626.0]]
Target sum:
8392
sum: 8382.0 Combination: (5084, 3298.0)
sum: 8382.85 Combination: (5084, 3298.85)
sum: 8383.0 Combination: (5084, 3299.0)
sum: 8392.0 Combination: (10, 5084, 3298.0)
sum: 8392.85 Combination: (10, 5084, 3298.85)
sum: 8393.0 Combination: (10, 5084, 3299.0)
sum: 8538.0 Combination: (5084, 156.0, 3298.0)
sum: 8538.85 Combination: (5084, 156.0, 3298.85)
sum: 8539.0 Combination: (5084, 156.0, 3299.0)
sum: 8538.43 Combination: (5084, 156.43, 3298.0)
sum: 8539.28 Combination: (5084, 156.43, 3298.85)
sum: 8539.43 Combination: (5084, 156.43, 3299.0)
There is a match: (10, 5084, 3298.0)
>>>