如何将列表与公共元素合并，其中这些元素本身是列表/元组?

Question

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

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 loop，并且返回错误AttributeError: 'int' object has no attribute '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)

Answer 2

试试这个循环:

newdata = []
for lst in data:
if newdata:
x = [i for i in lst if i not in newdata[-1]]
if x:
newdata.append(x)
else:
newdata.append(lst)
print(newdata)

输出:

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

Answer 3

已更新

试试这个,

def sort_list(data):
data = sorted(data, key=itemgetter(0))
return_list = []
for lst in data:
new_list = sorted(lst, key=itemgetter(0))
if not return_list:
return_list.append(new_list)
continue
if new_list[0] not in return_list[-1]:
return_list.append(new_list)
if new_list[0] in return_list[-1] and len(new_list) > 
len(return_list[-1]):
return_list.remove(return_list[-1])
return_list.append(new_list)
return return_list

所以你可以排序列表

data = [[],
[[0,1],[2,3]],
[[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]]
] 

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