在列表中列出類似的元素

Question

我有一個列表[ [0], [0,1], [1,2], [3] ]，我試圖將類似的元素組合在一起。我需要輸出爲[ [0,1,2], [3] ]。這是將列表中的類似元素分組。有沒有一個首選的方法來做到這一點？

Answer 1

你也可以遍歷每個輸入列表中的項目，構建羣體（如需要）：

def calculate_groups(data): 
    if not data: 
     return [] 
    groups = [set(data[0])] 
    for item in data[1:]: 
     item_set = set(item) 
     for group in groups: 
      if any(k in group for k in item): 
       group.update(item_set) 
       break 
     else: 
      groups.append(item_set) 
    return [list(group) for group in groups] 

這使用sets，any和list comprehension末。

例子：

>>> calculate_groups([ [0], [0,1], [1,2] ,[3] ]) 
[[0, 1, 2], [3]] 

Answer 2

我建議你使用的集列表，讓我們把它results_list，從一個空表開始，然後往裏面同時遍歷列表您的輸入列表：對於輸入列表的子列表中的每個項目，您都必須檢查它們是否屬於results_list中的任何集合。如果它們都不屬於，則只需添加一個包含該子列表元素的新集合。如果他們這樣做，則必須修改results_list合併至少存在一個項目的所有集合，包括在該集合中設置子列表的所有項目。

def regroup(groups_list): 
    results_list = [set(groups_list[0])] 
    for sub_list in groups_list[1:]: 
     current_items_set = set(sub_list) 
     groups_to_merge = [] 
     for group in results_list: 
      if any(k in group for k in sub_list): 
       groups_to_merge.append(group) 
     if not groups_to_merge: 
      # All of the items are new 
      results_list.append(current_items_set) 
     elif len(groups_to_merge) == 1: 
      # Current items belong only to one of the existing groups 
      groups_to_merge[0] = groups_to_merge[0].update(current_items_set) 
     else: 
      # The items belong to more than one group, merging is needed 
      new_set = reduce(lambda x, y: x.union(y), groups_to_merge) or set() 
      new_set.update(current_items_set) 
      # The new results_list will have the new merged set, excluding the separated ones 
      results_list = filter(lambda x: x not in groups_to_merge, results_list) + [new_set] 

    return [sorted(x) for x in results_list] 

例子：

input_list_1 = [[0], [0,1], [1,2], [3]] 
regroup(input_list_1) 
[[0, 1, 2], [3]] 

input_list_2 = [[0], [0,1], [1,2], [3], [0, 3]] 
regroup(input_list_2) 
[[0, 1, 2, 3]] 

Answer 3

這裏還有一個。比其他解決方案短一點。

def get_cliques(groups): 
    cliques = {} 
    for g in groups: 
     g = {*g}.union(*(cliques.get(i, []) for i in g)) 
     cliques.update({i: g for i in g}) 
    return {id(c): c for c in cliques.values()}.values() 

這段代碼背後的想法很簡單：一個派系的元素總是會共享clique集合對象。一個集合將包含所有已知在相應集團中的元素。所以最後我們只需要從cliques字典中獲得唯一的集合對象。我們使用內置的id函數返回對象內存地址（在CPython中）：cliques字典中的同一個集合中的不同元素包含相同的集合對象，因此我們可以將cliques字典壓縮爲較小的值，這些值將是唯一的。