將集合合併爲有向圖

Question

我的輸入是一組整數列表。意思是，每個集合都有一個我需要跟蹤的索引。那些（唯一的）集合包含整數，不同的集合可以具有一個或多個共同的整數元素（也可能兩個集合是相同的）。

我的目標是將這些集合不是作爲一個列表來表示，而是作爲一個樹狀結構，所以我可以消除多個集合共享的整數元素。該結構是具有人工根節點的有向圖。其他節點是集合中的整數。根節點最多有n個孩子（n是組數）。這些孩子實際上是來自不同組的第一個整數，並且必須由該算法添加。有幾個條件：

• 必須有可能通過樹中的一個路徑重新創建這樣一個集合。
• 通過樹的路徑必須是無歧義的，沒有頂點可以有多個孩子。
• 有一個例外：人工牙根節點被允許多生幾個孩子（那些孩子會成爲起點的路徑重新創建套）

顯然，這將是不可能消除所有重複，但我想找到一個算法，找到最可能的淘汰。這是我不得不尋求幫助。我可以通過手工完成，但不能用正式的算法來表達它，這在所有情況下都可行）。

編輯：但願這個小例子說明了這個問題更好：

我們有三個列表，list0 = [0,3,4,7,8], list1 = [1,2,3,6,7], list3 = [5,6,7,8]。這些列表的索引是來自根節點R的第一條邊的標題。在這個第一個邊緣之後，導致到沒有子節點的節點（在這個例子中它是所有三個節點的同一個節點，但不一定是這種情況）。此路徑上節點的所有標題都與相應的索引一起構成列表。

正如您所看到的，值7出現三次，值3,6和8每次兩次。所以最好的情況是擺脫5個不必要的節點。但是，根據我們的條件，沒有節點可以有多於一個孩子，並不總是可以擺脫所有重複。下圖顯示了一個可能的解決方案，其中重複的6和8無法解析。 [邊注：6或8可以與3進行交換，並且仍然具有一個12節點溶液]

Answer 1

我不知道現有算法來解決這個，但我認爲我看到了一些攻擊。首先，將您的圖形顛倒並使其成爲一棵簡單的樹，以爲根。接下來，請注意您的「列表」是無序的：它們會更好地工作（假設沒有值的重複）。

附註：你可以可以轉換爲單根問題 - 只需爲每個集合添加一個新的唯一符號。這將自動成爲根節點。

現在你可以用更像決策樹的東西來攻擊它。子樹的遞歸算法將產生可用的解決方案。您在分解的偏好嘗試首先應該由直覺來驅動，如

• 最頻繁出現在子樹的套
• 所有集合的最大公共子集的值。
• 將從問題中刪除最多元素的子集。例如，3個子集中的3個子集比2個子集中的4個子集更好。

最後一項不是在CS 101中解決的問題，它不是第一次罷工時保證的最佳解決方案。在過去的24小時內，我大部分都相信自己，沒有一個簡單的單一攻擊能夠爲您提供所有輸入的最佳解決方案。