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

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

Например, массив [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].


python list arrays subset-sum
person Elis Mower    schedule 05.12.2017    source источник
comment
Остерегайтесь этого partial=[]. Если вы можете реорганизовать свой код для возврата кортежей, вы можете вернуть набор кортежей, который удалит дубликаты за вас.   -  person Patrick Haugh    schedule 05.12.2017
comment
Что я действительно хочу, так это не только удалить подмножества, даже одно из их значений использовалось ранее, то есть упоминалось в списке отсортированных подмножеств.   -  person Elis Mower    schedule 05.12.2017
comment
@ElisMower Я не уверен, что именно вам здесь нужно. Я опубликовал ответ ниже, но похоже, что вы хотите чего-то другого   -  person RoadRunner    schedule 05.12.2017
comment
Например: [[2, 2], [1, 3], [1, 3], [1, 3], [1, 3], [1, 1, 2], [1, 1, 2]]. . Здесь, после первых двух подмножеств, я хочу, чтобы остались только [2,2] и [1,3].   -  person Elis Mower    schedule 05.12.2017
comment
Значит, вы хотите оставить только подсписки длины 2?   -  person RoadRunner    schedule 05.12.2017
comment
@RoadRunner, Ваш ответ очень помог. Спасибо :)   -  person Elis Mower    schedule 05.12.2017

Ответы (3)


arrow_upward
0
arrow_downward

Вы можете использовать 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() возвращал список не повторяющихся элементов, но приведенное выше также должно работать нормально.

person RoadRunner    schedule 05.12.2017

arrow_upward
0
arrow_downward

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

person chthonicdaemon    schedule 05.12.2017

arrow_upward
0
arrow_downward

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

Данные:

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))
person Aaditya Ura    schedule 05.12.2017