列表中元组的交集 - Python

Question

I have a list of tuples like this :

all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]

我需要取所有元组的交集并将它们合并。

The desired result = [{92, 242},{355, 403,436,489},{515, 517,859,701,775,634}]

这意味着要将交集的元组进行迭代联合。

我尝试将元组转换为集合并取交集，但没有成功。有什么想法吗？

- practitioner

Answer 1

这是一个网络问题，使用 networkx

import networkx as nx 
G=nx.Graph()
all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]
G.add_edges_from(all_tuples)
list(nx.connected_components(G))
Out[1216]: [{92, 242}, {355, 403, 436, 489}, {515, 517, 634, 701, 775, 859}]

- BENY

---

哇，从未想过这是网络问题。这个答案让我重新思考当前项目中其他复杂问题的解决方案。我希望能接受两个答案，但这些答案的执行速度更快。谢谢。 - practitioner

@nlp_practitioner 不用担心，这就是我们在这里的原因，不是吗？ :-) - BENY

这个问题几乎从来不是“这是一个图问题吗？”，而是“这是哪一个图问题呢？” :) - chepner

Answer 2

该解决方案建立了一个等价类列表，其中同属于一个元组的被视为等价关系。对于每个元组，我们将所有与该元组中某个元素匹配的集合列出。如果没有，则创建一个包含该元组的集合并添加到列表中。如果有一个，则更新该集合以包括元组的其他项。如果有多个，则从列表中删除它们，将它们与元组合并成一个集合，然后将该集合添加到列表中。

res = []
for t in all_tuples:
    matched = []
    for s in res:
        if s.intersection(t):
            matched.append(s)
    if not matched:
        res.append(set(t))
    elif len(matched) == 1:
        matched[0].update(t)
    else:
        res = [subl for subl in res if subl not in matched]
        res.append(set.union(*matched, t))

print(res)
# [{242, 92}, {489, 436, 355, 403}, {515, 517, 775, 634, 859, 701}]

- Patrick Haugh

---

这个答案也很好，但比 @W-B 的回答慢。谢谢。 - practitioner

Answer 3

只是因为为什么不呢，这里有一个只使用列表和元组的实现。

all_tuples=[(92, 242),(355, 403),(355, 436),(355, 489),(403, 436),(436, 489),(515, 517),(517, 859),(634, 775),(701, 859),(775, 859)]

curr_min, curr_max = all_tuples[0]
final = []
intermediate = [curr_min, curr_max]
for next_left, next_right in all_tuples[1:]:
    if curr_max >= next_left:
        intermediate.extend([next_left, next_right])
        curr_min, curr_max = min(curr_min, next_left), max(curr_max, next_right)
    else:
        final.append(set(intermediate))
        intermediate = []
        curr_min, curr_max = next_left, next_right
final.append(set(intermediate))

- Paritosh Singh