2組的聯合/交集，其中每組由其子集定義

Question

我們知道每個集合的定義來自其他集合的聯合。

例如

A = B聯合{1,2}

B = C工會d

C = {5,6}

d = {5,7}

E = {4}

則A = {1,2,5,6,7}

工會E = {1,2,4,5,6,7}

是否有任何有效的算法來做到這一點。假設工會的層次結構可能非常深，而子集可以經常改變（不是那麼多）。 我認爲應該有辦法最大限度地減少人工合作的數量。

Answer 1

因此，你有一個不斷變化的工會的層次結構？就像你的例子一樣，你只對一組的價值感興趣？

然後扁平化層次結構。也就是說，在你的例子中，你將一次遍歷層次結構來找到你的集合的集合，並存儲這個集合。

每當葉集發生變化時，爲了免除重新計算聯合，您可以跟蹤每個元素當前包含的集合數。如果樹葉集合發生變化，可以快速更新，而不需要查看任何未更改的樹葉集合。然後，頻率計數> 0的那些元素當前處於聯合中。

Answer 2

也許您正在尋找某種disjoint set數據結構？

Answer 3

關於這種情況的幾個問題。

第一個問題：這個「腳本」/「程序」需要運行多長時間？如果它不是太長，在執行聯合動作之前，簡單地存儲以前的聯合並檢查緩存可能是一個不錯的選擇。內存現在不是那麼貴:)。

第二個問題你應該問：在工會之前是否有特定順序的元素？如果它們不是，並且列表不止一次被訪問，那麼首先對列表進行排序可能非常有用（例如，當你只是列表的一半時，可以做出決定）。 Mergesort是有效連接兩個有序列表的強大技術。