Фильтрация дубликатов в комбинациях сумм подмножеств

Question

Учитывая массив, я нашел все комбинации подмножеств, которые равны целевой сумме, потому что я хочу максимально возможный массив.

Например, массив [1, 2, 2, 2] для целевой суммы "4" возвращает [[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]]

Тогда просто расплющить new_lst с itertools.chain.from_iterable и проверьте, не существует ли какого-либо элемента из исходного списка в этом плоском списке:

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

Примечание: вы можете сделать subset_sum() вернуть список не дубликатов элементов, но выше также должно работать нормально.

Answer 2

Вы можете сделать что-то вроде этого:

Данные это:

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

Одноканальное решение:

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))

Answer 3

Это не прямой ответ на ваш вопрос, а лучший алгоритм. Если вы ищете только один пример списка максимальной длины, который удовлетворяет вашему критерию суммы, вы должны сначала посмотреть на более длинные списки. Этот код использует 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)