從「包含」關係列表構建樹

-1

我有一個區域列表（A，B，C ...），每個區域都包含它們包含的城鎮列表（1，2，3，4）。從「包含」關係列表構建樹

請注意，這些不是直接的父母，同一個城鎮出現在包含它的任何區域。

A: 1 2 3 4 5 6 7 8 9 
B: 2 3 4 5 
C: 4 5 
D: 2 3 
E: 5 6 7

在我的情況，他們總是形成了獨特的層次關係，其中一個區域可以包含另一個區，不在任何一個子區域的城鎮一起。

A: B E 1 8 9 
B: C D 
C:  4 5 
D:  2 3 
E:  5 6 7

如果我們假設層次結構是獨一無二的，有人可以給我一個指針算法在任何通用的語言（或僞代碼）（我使用C＃）導出層次？

我開發了一些我認爲可行的東西，但我更喜歡比「這似乎工作」更具數學意義的東西。

如果沒有獨特的層次結構，我很高興能讓它中斷。

非常感謝

來源

2014-07-23 Tom West

有* *數百，甚至數千，在StackOverflow的算法問題。另外，我不認爲這個問題被認爲是「關於軟件開發的概念性問題」。如果我已經指定答案必須在C＃中，它會突然好嗎？（老實說，拆分看起來幾乎完全是任意的，除非沒有意外，程序員的StackExchange獲得的流量的1/100。在StackExchange的部分，這不是一個好的舉動......） –

此網站是爲了解決現有代碼中的錯誤，另一方面，看着StackOverflow常見問題我認爲你是對的，這可以很容易地發佈在這裏。我收回了我之前的建議，即將其移交給程序員並表示歉意。 – adamdc78

不需要道歉。可悲的是，我認爲-1（在任何地方）的問題註定會得到答案... –

我的解決方案，我認爲是正確的，但效率不高，是

（1）確定每個鎮直屬母公司區域：

對於每個鎮找到包含該城鎮的城鎮數量最少的地區。

（2）確定每個區域的直接父：

對於每一個區域，找到最小數量的城鎮，充分包含了（當然不包括本身），該區域的區域[完全包含=所有A區的小鎮也在B區]

再一次：這似乎工作假設如果一個區域X包含一個Y區包含的城鎮，則區域X包含Y區包含的所有城鎮，反之亦然。

在我的情況下，我通過修改步驟1對此進行了大量測試（但效率很低，但我的數據集很小（< 1,000個城鎮））。對於每個城鎮，我找到包含該城鎮的所有地區並對其進行排序按該地區的城鎮數量計算。然後檢查每個區域是否完整包含在列表中的下一個區域中。

如果任何人有一個已知的正確答案（或一個更有效，我會作出的貢獻表示感謝。）

來源

2014-07-25 14:06:02

從「包含」關係列表構建樹

回答

相關問題