如果輸入，我有一個這樣的串列串列
[[2,1], [1,3], [4,5], [6,8], [4,7]]
我怎樣才能找到一個/最大的子集，使得根本沒有重復/共享元素？
對于這個例子，答案是
[2,1], [4,5], [6,8]
或者
[1,3], [6,8], [4,7]
但無效的答案是
[2,1],[1,3],[4,5]
因為 1 在這里出現了兩次。
我目前的方法是一種遞回方法，它使用我選擇第一個元素或在構建子集時不選擇第一個元素的想法，但這種方法似乎太慢了。
我所擁有的：目前它只回傳最大子集的大小而不是實際子集的大小，但是一旦大小起作用，它應該很容易得到
def disjointSets(allSets):
maxCount = 0
used = set()
def findDisjoint(currCount, arr):
nonlocal maxCount
if not arr:
maxCount = max(maxCount, currCount)
return
elif arr[0][0] in used or arr[0][1] in used:
findDisjoint(currCount, arr[1:])
return
else:
used.add(arr[0][0])
used.add(arr[0][1])
findDisjoint(currCount 1, arr[1:])
used.clear()
findDisjoint(currCount, arr[1:])
return
findDisjoint(0, allSets)
return maxCount
uj5u.com熱心網友回復：
你這里有一個圖——數字是頂點，數字對是邊。
您的問題是找到最大的獨立邊集（不共享頂點的邊）。
這通常稱為最大匹配，這是眾所周知的問題，具有眾所周知的解決方案。Blossom 演算法是保證找到最佳答案的最簡單實用的方法。
uj5u.com熱心網友回復：
正如@MattTimmermans 所說，您在這里擁有的是一個無向圖，其中每個數字都是一個節點，每一對都是一條邊。匹配是一組不共享節點的邊，您的作業是找到最大匹配，即包含最大邊數的匹配。
有一個名為networkx的 Python 包，它處理網路，特別是圖形。其中有一個名為max_weight_matching實作 Edmonds 的開花演算法的方法。
在您的示例中：
import networkx as nx
G = nx.Graph()
G.add_edges_from([[2,1], [1,3], [4,5], [6,8], [4,7]])
out = nx.max_weight_matching(G)
輸出：
{(8, 6), (4, 7), (1, 3)}
uj5u.com熱心網友回復：
可能是，但我不確定它是否很快！更新 ！
matris = [[2,1], [1,3], [4,5], [6,8], [4,7]]
print(matris)
def select(item, matris, selected):
x = item[0]
y = item[1]
if x != y:
selected.append(item)
i = 0
while i < len(matris):
if x in matris[i] or y in matris[i]:
matris.pop(i)
i -= 1
i = 1
if len(matris) != 0:
select(matris[0], matris, selected)
return selected
print("=================")
max_count = 0
for i in range(len(matris)//2 1 if len(matris) % 2 == 0 else len(matris)//2):
selected = select(matris[i], matris.copy(), [])
if len(selected) >= max_count:
max_count = len(selected)
print(selected)
print("=================")
print("Max Length => " str(max_count))
print("=================")
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/419215.html
標籤：