python中和大于值的最小子集

Question

对于不同维度的列表，最快的方法是什么，求和大于或等于特定值的所有最小子集？

因此，如果设置和值是

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10

解决方案是

res = [[10],[11]]

或者再次：

A = [[1,10],[1,2,3,4],[5,6],[10,10],[1000,12,1],[1,10,11]]
value = 10
res = [[1,10],[10,10]]

提前感谢

Answer 1

您可以使用以下python代码：代码在a中查找长度列表然后按升序检查子列表，即大小为1、大小为2、大小为4的子列表。请注意，如果结果中已经包含较小的子列表，则代码不会检查较大的子列表。

A = [[1],[1,2,3,4],[5,6],[10],[1000,12],[11]]
value = 10
lens = list(set([len(i) for i in A]))   #result = [1,2,4]
res = []
for l in lens:
if len(res) == 0: 
for i in A: 
if len(i) == l: 
if sum(i) >= value: 
res.append(i)
print(res)   #result = [[10], [11]]   

Answer 2

以下是我在(2^nd(评论中所说的内容。使用简单的列表理解找出所有满足条件的子列表：

>>> lists = [[1], [1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]
>>> value = 10
>>>
>>> [l for l in lists if sum(l) >= value]
[[1, 2, 3, 4], [5, 6], [10], [1000, 12], [11]]

因此，我们有一些可以工作但可能被认为很慢的东西(好吧，不是这个特定的例子，但对于更大的输入列表(。它是慢的，因为它搜索所有满足条件的子列表，而实际上只应该尝试长度为1的子列表(在这种情况下(。

我脑海中浮现的1^st是根据子列表的长度对输入列表中的子列表进行排序。但排序本身也可能很慢，实际上我们只需要对它们进行分组。一种方法是使用字典，其中键是子列表的长度，对于特定的键，值是一个包含所有具有该长度的子列表的列表：

>>> d = {}
>>> for l in lists:
...     d.setdefault(len(l), []).append(l)
...
>>> d
{1: [[1], [10], [11]], 4: [[1, 2, 3, 4]], 2: [[5, 6], [1000, 12]]}
>>>
>>> ret = []
>>>
>>> for i in sorted(d):  # Traverse the (sorted) lengths
...     for l in d[i]:
...         if sum(l) >= value:
...             ret.append(l)
...     if ret:  # Once a specific length was handled, if there are some results, simply stop
...         break
...
>>>
>>> ret
[[10], [11]]

或者，作为一个函数：

def filter_sublists(sublists, min_sum_threshold):
d = {}
for l in sublists:
d.setdefault(len(l), []).append(l)
ret = []
for i in sorted(d):
for l in d[i]:
if sum(l) >= min_sum_threshold:
ret.append(l)
if ret:
break
return ret