如何从子集列表中筛选出唯一的组合

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]的组合。我怎么只打印其中一个？干杯！！在

我知道Q值可能没有反映出我真正想要的，所以请随时改进它。在

Answer 1

不要在列表中多次出现数字，只需添加（number，multiplicity）的元组 所以您的输入将变成[(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]])

或者，保存“部分”列表和“丢弃”列表可能更容易。那你可以查一下

^{pr2}$

Answer 2

使用元组（不可变的）而不是列表。然后，可以将它们的列表转换为一个集合（这将删除重复项），最后将集合转换回列表。在

ielist(set([(3,4,5),(3,4,5),(3,5,4),(3,6,3) ...]))产生{}

您可以使用map将项与元组进行转换：

map(tuple, your list of lists)

以及

^{pr2}$