得到最少的沒有。串列（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
uj5u.com熱心網友回復：
您的問題可以很容易地簡化為最大權重獨立集，其中：
- 頂點是 L2 中的串列；
- 如果兩個串列至少有一個共同元素，則它們共享一條邊；
- 串列的權重是它的長度。
可悲的是，最大獨立集問題是 NP 難的，并且難以近似。
一個更容易的問題是最大獨立集。最大獨立集問題的解決方案是最大獨立集的近似解決方案，盡管不一定是好的解決方案。
用模塊 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使用隨機演算法：您可以多次運行它，并保持找到的最佳解決方案。
資源
- networkx.maximal_independent_set；
- dwave_networkx.maximum_weighted_independent_set；
- 用于精確加權最大獨立集的 Python 庫？;
- 在任意圖中找到最大權重獨立集的啟發式方法？
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/411304.html
標籤：
上一篇：歸并排序中的遞回和While回圈
下一篇：連接樹資料-如何簡化我的代碼？