リストのリストに類似の要素をグループ化する

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を編集して、少なくとも1つのアイテムが存在するすべてのセットをマージしなければなりません。その中にサブリストのすべてのアイテムを設定します。

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() 

このコードの背後にあるアイデアは簡単です：1つのクリークの要素は常にcliqueオブジェクトを共有します。セットには、対応するクリークに存在することが既に分かっているすべての要素が含まれます。だから最後にcliques辞書からユニークなセットオブジェクトを取得する必要があります。私たちはid関数を使ってオブジェクトメモリアドレス（CPythonで）を返します。cliquesディクショナリ内の同じクリークと異なる要素は同じセットオブジェクトを含んでいますので、値が一意になるようにより小さい値にcliquesをスクッシュすることができます。