求和具有约束的列表中元素的组合

Question

我有一个嵌套列表g=[[2, 1],[1, 3],[8, 1]]。我想要一个列表，其中：

列表的每个内部元素最多加上另外两个内部元素。以下是过程，因此需要输出：

# 1= a single element like g[0][1]
# 2= a single element like g[0][0] or can be added by two inner elements like g[0][1]+g[1][0]
# 3= a single g[1][1], adding two elements g[0][0]+g[1][0] or at most three g[0][1]+g[1][0]+g[2][1] 
.
.
.
# 13= g[0][0]+g[1][1]+g[2][0]

因此，最终结果将是一份清单。请注意，结果中不可能有7，因为没有任何组合(没有替换(可以加起来达到7。此外，从每个元素中最多可以选择一个内部值。

expected_result = [1,2,3,4,5,6,8,9,10,11,12,13]

这就是我所做的，但它不包含1和2，还包含7:

g=[[2, 1],[1, 3],[8, 1]]
from itertools import product
maxx = []
# Getting all possible combination of adding at most 3 elements (=length of g)
for i in list((product([i for j in g for i in j], repeat=len(g)))):
maxx.append(sum(i))
# Narrowing the result so it doesn't exceed the maximum combination which is sum([2,3,8])
print([i for i in set(maxx) if i<=sum(max_list)])
>>> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]

感谢您的帮助。

Answer 1

数据的形状/格式似乎是在转移注意力。只需将列表展平，并查找展平列表中1、2或3个元素的每个组合的唯一和。使用itertools.chain使列表变平，使用itertools.combinations创建组合，再次使用itertools.chain组合组合，并使用set返回唯一结果：

>>> import itertools
>>> g = [[2, 1],[1, 3],[8, 1]]
>>> flattened = itertools.chain(*g)
>>> flattened
[2, 1, 1, 3, 8, 1]
>>> list(set(map(sum,
itertools.chain(itertools.combinations(flattened, 1), 
itertools.combinations(flattened, 2),
itertools.combinations(flattened, 3)))))
[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]

编辑：问题已更改为包含以下约束：

此外，每个元素最多可以选择一个内部值。

这意味着你无法使列表变平。以下是一个满足新约束的更新解决方案：

>>> list(set(map(sum,
itertools.chain.from_iterable(itertools.combinations(p, n)
for n in range(1,4)
for p in itertools.product(*g)))))
[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]
>>> g = [[2, 1],[1, 3],[8, 1],[14, 15]  # should not produce 29 as an answer
>>> list(set(map(sum,
itertools.chain.from_iterable(itertools.combinations(p, n)
for n in range(1,4)
for p in itertools.product(*g)))))
[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26]

Answer 2

我现在能想到的最简单的实现：

def fun(numbers):
all_numbers = [x for y in numbers for x in y]
output = list(set(all_numbers))
for x in all_numbers:
for y in all_numbers:
if x is not y:
output.append(x + y)
for z in all_numbers:
if y is not x and y is not z and x is not z:
output.append(x + y + z)
return list(set(output))

print(fun([[2, 1], [1, 3], [8, 1]]))

上面的代码打印

[1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13]