基於重複項目的組Python列表

這個問題非常類似於這個Group Python list of lists into groups based on overlapping items，實際上它可以被稱爲重複項。基於重複項目的組Python列表

基本上，我有一個子列表的列表，其中每個子列表包含一些整數（這個數字在子列表中不相同）。我需要將所有共享一個或多個整數的子列表分組。

我之所以提出一個新的問題，是因爲我試圖讓Martijn Pieters的great answer沒有運氣。

這裏的MWE：

def grouper(sequence): 
    result = [] # will hold (members, group) tuples 

    for item in sequence: 
     for members, group in result: 
      if members.intersection(item): # overlap 
       members.update(item) 
       group.append(item) 
       break 
     else: # no group found, add new 
      result.append((set(item), [item])) 

    return [group for members, group in result] 


gr = [[29, 27, 26, 28], [31, 11, 10, 3, 30], [71, 51, 52, 69], 
     [78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81], 
     [86, 68, 67, 84]] 

for i, group in enumerate(grouper(gr)): 
    print 'g{}:'.format(i), group

和輸出我得到的是：

g0: [[29, 27, 26, 28]] 
g1: [[31, 11, 10, 3, 30]] 
g2: [[71, 51, 52, 69]] 
g3: [[78, 67, 68, 39, 75], [84, 67, 78, 77, 81], [86, 68, 67, 84]] 
g4: [[86, 84, 81, 82, 83, 85]]

最後一組g4應該已經合併g3，因爲它們內部列表共享項目81， 83和84，甚至一個重複元素應該足以讓它們合併。

我不確定我是否錯誤地應用了代碼，或者代碼出了問題。

來源

2015-08-17 Gabriel

我不認爲你是做錯任何事情;該代碼不處理由於遇到事情而發生級聯合並的情況。（例如'石斑魚（[[1,1]，[1,2]，[2,2]]）''但石斑魚（[[1,1]，[2,2]，[1,2]] ）'沒有。 – DSM

您可以描述要作爲集合整合或作爲連接組件問題進行的合併。我傾向於使用現成的集合合併算法，然後根據特定情況進行調整。例如，IIUC，你可以使用類似

def consolidate(sets): 
    # http://rosettacode.org/wiki/Set_consolidation#Python:_Iterative 
    setlist = [s for s in sets if s] 
    for i, s1 in enumerate(setlist): 
     if s1: 
      for s2 in setlist[i+1:]: 
       intersection = s1.intersection(s2) 
       if intersection: 
        s2.update(s1) 
        s1.clear() 
        s1 = s2 
    return [s for s in setlist if s] 

def wrapper(seqs): 
    consolidated = consolidate(map(set, seqs)) 
    groupmap = {x: i for i,seq in enumerate(consolidated) for x in seq} 
    output = {} 
    for seq in seqs: 
     target = output.setdefault(groupmap[seq[0]], []) 
     target.append(seq) 
    return list(output.values())

這給

>>> for i, group in enumerate(wrapper(gr)): 
...  print('g{}:'.format(i), group) 
...  
g0: [[29, 27, 26, 28]] 
g1: [[31, 11, 10, 3, 30]] 
g2: [[71, 51, 52, 69]] 
g3: [[78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81], [86, 68, 67, 84]]

（因爲使用了字典的順序不能保證。）

來源

2015-08-17 19:52:37 DSM

精彩的回答帝斯曼，你甚至解決了我不知道的問題。謝謝！ – Gabriel

現貨！ - 我想是這樣。我寫了任務和迭代Python解決方案，其他成員Rosetta Code與其他所有例子都非常充實。瀏覽網站@Gabriel，還有更多來自:-) – Paddy3118

聽起來像設置合併，如果你把每個子列表變成一個集合，而不是你對內容感興趣的話，那麼這些集合就是最好的數據結構選擇。請參閱：http://rosettacode.org/wiki/Set_consolidation

來源

2015-08-17 19:42:08 Paddy3118

基於重複項目的組Python列表

回答

相關問題