python - 如何将列表与常见元素合并，其中这些元素本身是列​​表/元组？

Question

我有这个嵌套列表，我需要以某种方式循环它以合并具有公共(public)元素的内部列表(其中这些元素本身就是列表)。这是一个简化的数据，具有现有原始数据的模式:

data = [
        [[0,1],[2,3],[4,5]], 
        [[2,3],[4,5]], 
        [[4,5]], 
        [[6,7],[8,9],[10,11]], 
        [[8,9],[10,11]], 
        [[10,11]], 
        [[12,13],[14,15],[16,17],[18,19],[20,21]], 
        [[14,15],[16,17],[18,19],[20,21]], 
        [[16,17],[18,19],[20,21]],
        [[18,19],[20,21]],
        [[20,21]]
       ]  

我想获得一个合并的嵌套列表，如下所示:

merged = [
      [[0,1],[2,3],[4,5]], 
      [[6,7],[8,9],[10,11]], 
      [[12,13],[14,15],[16,17],[18,19],[20,21]]
     ]

下面是我尝试过的，不幸的是，它没有超出第二个内部for循环，并且返回错误AttributeError:'int'对象没有属性'values':

tmp = {}
for subl in original:
    subl = list(set(subl))                        # Eliminating duplicates by first converting to a set
    subl = dict(zip(subl, range(len(subl))))      # Create dictionary from list
    sublswitch = {y:x for x,y in subl.items()}    # Swap dictionary key for values and vice versa                
    ii = 0
    for key in sublswitch:            
        tmp.setdefault(key.values(), set()).add(list(key.values())[ii])
        ii += 1                                         

out = []
for k, v in tmp.items():
    out.append([[k, i] for i in v])

Answer 1

这是一个使用 O(n) 额外空间的解决方案，该空间跟踪已使用哈希表添加的所有子列表(因此，所有查找都只是 O(1))。

added = set()
merged = []

for item in data:
    filtered = list(filter(lambda value: value not in added, map(tuple, item)))
    if filtered:
        added.update(filtered)
        merged.append(list(map(list, filtered)))

print(merged)

输出

[[[0, 1], [2, 3], [4, 5]], [[6, 7], [8, 9], [10, 11]], [[12, 13], [14, 15], [16, 17], [18, 19], [20, 21]]]

---

更新

上面的解决方案只能防止重复的列表项在下一个列表中再次出现。在这里，我们不仅会阻止它们再次发生，还会将它们合并到现有的事件上。因此，该算法的时间复杂度有点O(n^2)。

merged = []

for item in data:
    item_set = set(map(tuple, item))
    for result in merged:
        if result & item_set:
            result.update(item_set)
            break
    else:
        merged.append(item_set)

merged = [sorted(map(list, item)) for item in merged]
print(merged)