匹配两个列表中的列表元素,这两个列表总和相同

Question

我有两个数字列表(A和B),A中某些元素的组合应该与B中某些元素组合的总和相同.当匹配组时,匹配的元素将从其列表中删除,直到所有组合都匹配.

例如,使用两个列表:

A = [7, 8, 12, 300, 350]
B = [3, 4, 20, 150, 500]

匹配组的总和将是:

{7: [{'A': [7], 'B': [3, 4]}],
 20: [{'A': [8, 12], 'B': [20]}],
 650: [{'A': [300, 350], 'B': [150, 500]}]}

到目前为止我解决这个问题的天真方法是从每个列表中得到所有可能组合的总和(pow(2,len(mylist)) - 1),在两组所有组合之间做一组交集,然后删除元素按顺序排列,直到占用所有元素.

有谁知道一个更有效的算法来实现这一目标？扩展到每个列表的所有可能组合然后进行集合交叉可以变大.

这是天真的方式:

def getCombos(stuff):
    res = []
    for L in range(1, len(stuff) + 1):
        for subset in itertools.combinations(stuff, L):
            res.append(subset)
    return res

Acombo = getCombos(A)
Bcombo = getCombos(B)
AcomboSum = [sum(tup) for tup in Acombo]
BcomboSum = [sum(tup) for tup in Bcombo]

sumint = sorted(set(AcomboSum).intersection(set(BcomboSum)))

Arem = [a for a in A]
Brem = [b for b in B]

d = collections.defaultdict(list)

for s in sumint:
    idx = sumint.index(s)
    Avals = Acombo[AcomboSum.index(s)]
    Bvals = Bcombo[BcomboSum.index(s)]

    if set(Avals).issubset(set(Arem)) and set(Bvals).issubset(set(Brem)):
        d[s].append([Avals, Bvals])
        for v in Avals: Arem.pop(Arem.index(v))
        for v in Bvals: Brem.pop(Brem.index(v))
    else:
        continue

print(d)

Answer 1

按反向降序对两个数组进行排序。

然后计算数组 A 中的所有总和并按反向降序排序。

如果 A[n] 表示数组 A 中的所有元素

B[m]表示数组B中的所有元素

sum_A[n!] 表示 A 中所有可能的元素之和。

sum_A.sorted(reverse=True) 表示该数组按降序排序。

创建一个新数组 B_start[n!] 并存储 B 中小于 sum_A[i] 的第一个元素的索引 i。

现在，对于任何 sum_A[i] 元素，您只需考虑 B 中从 B[ B_start[i] ] 到 B[m] 的元素作为总和的组合

注意：这仅在数组中的所有数字均为正数时才有效。