过滤子集和组合中的重复项

Question

给定一个数组，我发现子集的所有组合等于目标总和，那是因为我想要尽可能大的数组。

例如数组[1, 2, 2, 2]为目标和“4”returns [[2 , 2], [2, 2], [2, 2]].

subsets = []

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)
    if s == target:
        subsets.append(partial)
    if s >= target:
        return
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i + 1:]
        subset_sum(remaining, target, partial + [n])

subsets.sort()
subsets.reversed()

如何删除子集列表中曾经提到的值？在上面的例子中，我怎么能只有一个 [2,2].

然后，显示不在此最终列表中的初始数组的值？在上面的例子中 [1].

Answer 1

您可以使用 itertools.groupby 删除重复列表：

>>> import itertools
>>> lst = [[2, 2], [2, 2], [2, 2]]
>>> lst.sort()
>>> new_lst = list(k for k,_ in itertools.groupby(lst))
>>> print(new_lst)
[[2, 2]]

然后简单地用 itertools.chain.from_iterable 压平 new_lst 并检查初始列表中的任何元素是否不存在于这个压平的列表中：

>>> initial = [1,2,2,2]
>>> print([x for x in initial if x not in itertools.chain.from_iterable(new_lst)])
[1]

注意： 您或许也可以将 subset_sum() return 设为非重复项目的列表，但以上内容应该也能正常工作。

Answer 2

这不是您问题的直接答案，而是一种更好的算法。如果您只是在寻找满足总和标准的最大长度列表的一个示例，那么您应该首先查看更长的列表。此代码将 itertools 用于组合位，并在找到最长列表时停止。

numbers = [1, 2, 2, 2]
taget = 5

for size in reversed(range(1, 1 + len(numbers))):
    for c in itertools.combinations(numbers, size):
        if sum(c) == target:
            break
    else:
        continue
    break

c 现在包含最长的子集作为元组 (1, 2, 2)

Answer 3

你可以这样做：

Data is :

data=[1, 2, 2,2]
import itertools
your_target=4

One line solution:

print(set([k for k in itertools.combinations(data,r=2) if sum(k)==your_target]))

输出：

{(2, 2)}

或者如果你使用函数更好：

def targeted_sum(data,your_target):
    result=set([k for k in itertools.combinations(data,r=2) if sum(k)==your_target])
    return result

print(targeted_sum(data,4))

过滤子集和组合中的重复项

Filtering the duplicates in subset sum combinations

python

arrays

list

subset-sum