Как отфильтровать уникальные комбинации из списка подмножеств

Question

Я пытался придумать скрипт для реализации Subset sum Prob с некоторой помощью от первого скрипта this post. Итак, теперь я запускаю свой сценарий, я получаю это:

maci:python sant$ ./subsetSum.py -n3,4,5,6,7,8,9,3,4,5 -t12 
[3, 4, 5] => 12 
[3, 4, 5] => 12 
[3, 5, 4] => 12 
[3, 6, 3] => 12 
[3, 9] => 12 
[3, 4, 5] => 12 
[4, 5, 3] => 12 
[4, 8] => 12 
[4, 3, 5] => 12 
[5, 7] => 12 
[5, 3, 4] => 12 
[7, 5] => 12 
[8, 4] => 12 
[9, 3] => 12 
[3, 4, 5] => 12 

Это работает нормально. Но как отфильтровать только уникальное подмножество? В результате 1, 2 и 15 точно совпадают, и есть другие 6, которые являются комбинацией [3,4,5]. Как напечатать только один вместо всех? ура !!

PS. Я знаю, что Q, вероятно, не отражает то, что я хочу, поэтому не стесняйтесь его улучшать.

Answer 1

Вместо того, чтобы иметь номера в вашем списке несколько раз, просто добавьте кортежи (число, кратность) , поэтому ваш вход будет [(3, 2), (4, 2), (5, 2), (6, 1), (7, 1), (8, 1), (9, 1)].

Это позволяет легко создавать ваши подмножества без дубликатов. Вы могли бы сделать нечто вроде:

for i in n[1]: 
    subset_sum_recursive(remaining, target, partial + i * [n[0]]) 

В качестве альтернативы может быть проще, чтобы сохранить не только свой «частичный» список, но и «отбрасывается» список. Затем вы можете проверить

if(n not in discarded) 
    subset_sum_recursive(remaining,target,partial + [n]) 

Answer 2

Используйте кортежи (которые являются неизменяемыми) вместо списков. Затем вы можете преобразовать список из них в набор (который удаляет дубликаты) и, наконец, преобразовать набор в список.

т.е. list(set([(3,4,5),(3,4,5),(3,5,4),(3,6,3) ...])) производит [(3,4,5),(3,5,4),(3,6,3) ...]

Вы можете использовать карту, чтобы преобразовать элементы и из кортежей:

map(tuple, your list of lists) 

и

map(list, your list of tuples)