时间戳

首页 > 解决方案 > 按共享元素对列表进行分组

python - 按共享元素对列表进行分组

问题描述

假设我有以下子列表列表：

l = [['a', 'b'], 
 ['a', 'c'], 
 ['b', 'c'],
 ['c', 'd'],  
 ['e', 'f'], 
 ['f', 'g'], 
 ['x', 'y']]

我的目标是将该列表重新排列为“存储桶”，以使存储桶中的每个子列表与存储桶中的至少一个其他子列表共享一个元素，并且不与不同存储桶中的任何子列表共享任何元素。用语言很难理解这一点，但在这种情况下，所需的结果将是：

result = [
    [
        ['a', 'b'],
        ['a', 'c'],
        ['b', 'c'],
        ['c', 'd']
    ],
    [
        ['e', 'f'],
        ['f', 'g']
    ],
    [
        ['x', 'y']   
    ],
]

这里的想法是['a','b']进入 Bucket 1.与and['a','b']共享元素，因此这些元素也进入 Bucket 1。现在还与当前在 Bucket 1 中的元素共享一个元素，因此它也被添加到 Bucket 1 中。之后，不再有与​​ Bucket 1 中的元素共享的子列表，因此我们打开一个新的 Bucket 2，以. 与 共享一个元素，因此也进入 Bucket 2。然后我们完成了 Bucket 2。得到它自己的 Bucket 3。['a', 'c']['b', 'c']['c', 'd']c['e', 'f']['e', 'f']['f', 'g']['x', 'y']

我知道如何递归地做所有这些，但是l非常大，我想知道是否有更快的方法将元素组合在一起！

标签： pythonlistsortinggrouping

解决方案

这段代码似乎工作：

l = [
 ['a', 'b'], 
 ['a', 'c'], 
 ['b', 'c'],
 ['c', 'd'],  
 ['e', 'f'], 
 ['f', 'g'], 
 ['x', 'y']]
 
l2 = []

# merge lists to sets
for x in l:
  for x2 in l2:
     if len(x2 & set(x)):
         x2 |= set(x)
         break
  else:
     l2.append(set(x))

# output lists
d = {i:[] for i in range(len(l2))}

# match each list to set
for x in l:
  for k in d:
    if len(set(x) & set(l2[k])):
       d[k].append(x) 

# merge dictionary values
fl = [v for v in d.values()]

print(fl)

输出

[[['a', 'b'], 
  ['a', 'c'], 
  ['b', 'c'], 
  ['c', 'd']], 
 [['e', 'f'], 
  ['f', 'g']], 
 [['x', 'y']]]

推荐阅读