寻找最小号列表（l2）中的子列表在另一个列表（l1）中具有最大元素。答案应至少包含“否”。子列表的

Question

得到最少的没有。列表 (l2) 中的子数组的数量，它们总共具有原始列表 (l1) 中元素的最大数量。子数组元素（答案）不应超过L1元素，这意味着如果2在L1中重复2次，那么在包含所有子数组的答案中2的数量不能超过2.

示例 1

L1 = [2,3,5,6]
L2 = [[3], [2, 5], [2, 6], [3, 5], [5, 6], [2, 3, 6]]

上面例子的答案是[[2, 6], [3, 5]]

示例 2

L1 = [2,3,5,6]
L2 = [[3], [2, 5], [2, 6], [5, 6], [2, 3, 6]]

上面例子的答案是[[2, 3, 6]]

我尝试了以下方法，但由于 res_comb 需要时间，因为如果 res 的长度更长，它将有很多组合，让我们假设 40。我需要更快的东西。

def return_similar(res,search):  
    res_comb = [list(map(list,combinations(res,i))) for i in range(1,len(res)+1)]
    dict_search = defaultdict(int)
    for x in search:
        dict_search[x]+=1
    match = []
    maxs=0
    for x in res_comb:
        for val in x:
            final_res = []
            for inner in val:
                final_res.extend(inner)
            dict_final_res = defaultdict(int)
            for x in final_res:
                dict_final_res[x]+=1
            count=0
            counter=0
            for x in set(final_res):
                if dict_search[x]<dict_final_res[x]:
                    counter=1
                    break
            if counter==0:
                count = len(final_res)
                if count>maxs:
                    maxs=count
                    match.clear()
                    match.append(val)
                elif (count==maxs) and (count!=0) :
                    match.append(val)
                    
    return match

Answer 1

你的问题很容易简化为最大权重独立集，其中：

顶点是L2中的列表；
如果两个列表至少有一个共同元素，则它们共享一条边；
列表的权重就是它的长度。

可悲的是，最大独立集问题是 NP-hard，很难近似。

一个更简单的问题是最大独立集。 最大独立集问题的一个解是最大独立集的一个近似解，虽然不一定好

寻找一个 最大独立集 模块 networkx:

from networkx import Graph
from networkx import maximal_independent_set
from itertools import combinations

L2 =  [[3], [2, 5], [2, 6], [5, 6], [2, 3, 6]]
vertices = [frozenset(u) for u in L2]

G = Graph()
G.add_nodes_from(vertices)
G.add_edges_from((u,v) for u,v in combinations(vertices, 2) if u.intersection(v))

mis = maximal_independent_set(G)

print(mis)
# [frozenset({3}), frozenset({5, 6})]

如您所见，算法找到了 [{3}, {5,6}]，这是次优的：[{2,5}, {3,6}] 会更好。

请注意 networkx.maximal_independent_set 使用随机算法：您可以运行多次，并保留找到的最佳解决方案。

寻找最小号列表（l2）中的子列表在另一个列表（l1）中具有最大元素。答案应至少包含“否”。子列表的

Finding minimum no. of sub-list from the list(l2) which have maximum elements in a other list(l1). Answer should contain least no. of sub-list

arrays

recursion

list

dynamic

python-3.x

资源