我想在 python 中創建一個 TransitiveClosure() 函式，它可以輸入一個字典并輸出一個傳遞閉包的新字典。
例如R = {1: [3], 2: [4], 3: [], 4: [1]}將輸出R R = {1 : [3], 2 : [1, 3, 4], 3 : [], 4 : [1, 3]}.
我知道傳遞屬性是a->b, b->cthan a->c。
我不能使用矩陣，實際上我需要創建一個新字典。我嘗試將字典轉換為包含集合的串列，但這也有其問題。有人可以幫忙嗎？
謝謝你！
def transitiveClosure(r):
d ={}
R = list(r.items())
# loop for a,b
for a, b in R:
#loop for c, d
for c, d in R:
# checks if b = c and if a, d are in R
if b == c and ((a, d) not in R):
print("Not Transitive")
return False
print("is Transitive")
return True
這將告訴我字典是否可傳遞，我很難嘗試使用此邏輯創建新字典。由于我將輸入字典轉換為集合串列，我是否需要將元素添加到串列然后將其轉換回字典？
uj5u.com熱心網友回復：
我可以想到使用遞回函式的以下解決方案
def reachable_items(R,k):
ans = R[k]
if ans != []:
for v in ans:
ans = ans reachable_items(R,v)
return ans
def transitive_closure(R):
ans = dict()
for k in R.keys():
ans[k] = reachable_items(R,k)
return ans
例子：
>>> R1 = {1: [3], 2: [4], 3: [], 4: [1]}
>>> transitive_closure(R1)
{1: [3], 2: [4, 1, 3], 3: [], 4: [1, 3]}
>>> R2 = {1:[2],2:[],3:[4,5],4:[1],5:[]}
>>> transitive_closure(R2)
{1: [2], 2: [], 3: [4, 5, 1, 2], 4: [1, 2], 5: []}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/330469.html
上一篇：將資料幀拆分為字典字典