這個數據結構有一個友好的名字嗎？

雖然關於在Python的機器學習算法的特徵選擇器的工作，我生成用下面的代碼的數據結構：這個數據結構有一個友好的名字嗎？

# Perform set partitioning on the results 
groups = [] 
for t in results: 
    (jthName,kthName) = t 
    jthGroup = -1 
    kthGroup = -1 

    # Just a simple list of hashes with online merging 
    for idx,group in enumerate(groups): 
     if jthName in group: 
      jthGroup = idx 
     if kthName in group: 
      kthGroup = idx 
    if jthGroup == kthGroup: 
     if jthGroup == -1: # Implicit: "and kthGroup == -1" 
      groups.append(set((jthName,kthName))) 
    elif jthGroup != kthGroup: 
     if kthGroup == -1: 
      # Merge kthName into jthGroup 
      groups[jthGroup].add(kthName) 
     elif jthGroup == -1: 
      # Merge jthName into kthGroup (redundant if naturally-ordered) 
      groups[kthGroup].add(jthName) 
     else: 
      # Merge jthGroup and kthGroup, since we have a connecting pair 
      merged = set() 
      merged.update(groups[jthGroup]) 
      merged.update(groups[kthGroup]) 
      groups.remove(groups[jthGroup]) 
      groups.remove(groups[kthGroup]) 
      groups.append(merged)

凡我輸入，results，是元組的列表，{2}和groups是一組列表。請注意，我的代碼在這裏不一定有效。它僅用於說明目的。

我的數據結構，groups，具有以下屬性：

對於每個(jthName,kthName)：
- 如果發現(jthName,kthName)既不元素中包含的任何設置，我們的列表中創建set((jthName,kthName))集。
- 如果在一個包含集合中找到(jthName,kthName)中的一個，則將未被發現的元素合併到該集合中。
- 如果在不同的集合中找到(jthName,kthName)的每個元素，則將這兩個引用的集合合併爲一個集合。
循環不變：jthName和kthName不能包含在一組以上。

我給這個數據結構的理由是創建一個未知的組連接nodegraphs，其中每個唯一元素的名稱是一個節點，並且每個獨特的一對是邊緣的平坦分解。我的理由是我的圖表是不完整的，我需要這個視圖來選擇只有每個圖的已知成員才能進入一個算法，該圖將連通性和邊緣的方向性（也就是表示DAGs的完整集合由數據）。但是，我離題了。

是否有一個由變量groups表示的數據結構的友好名稱？如果是這樣或者如果沒有，是否有更多的時間或空間有效的方法來執行這種分解？

來源

2012-03-06 MrGomez

可以在http://cstheory.stackexchange.com/更合適。我沒有在那裏發表，因爲據我所知，這是一個從業人員的本科水平問題。 – MrGomez 2012-03-06 01:35:38

我認爲你要找的東西叫做Disjoint-set data structure。

它在做Kruskal's時經常使用，因爲它允許你在nlog * n（實際小於）時間內進行n次查找，如果你使用路徑壓縮實現不相交集數據結構。

這是非常合理的實現，我認爲維基頁面的僞代碼本身很適合python。如果您需要更多幫助，請撥打this SO question might help。

如果使用的是並查集，你的代碼應該是這樣的：

for t in results: 
    (jName, kName) = t 

    union(jName, kName)

來源

2012-03-06 01:43:58

這個數據結構有一個友好的名字嗎？

回答

相關問題