python - 使用元组创建元组组

Question

让我们考虑以下元组列表:

[('AUD', 'M6A'),
 ('CHF', 'E7'),
 ('CHF', 'EUR'),
 ('CHF', 'M6E'),
 ('E7', 'CHF'),
 ('E7', 'EUR'),
 ('E7', 'M6E'),
 ('EMD', 'ES'),
 ('EMD', 'RTY'),
 ('ES', 'EMD'),
 ('ES', 'NQ'),
 ('EUR', 'CHF'),
 ('EUR', 'E7'),
 ('EUR', 'M6E'),
 ('GBP', 'M6B'),
 ('GF', 'LE'),
 ('LE', 'GF'),
 ('M6A', 'AUD'),
 ('M6B', 'GBP'),
 ('M6E', 'CHF'),
 ('M6E', 'E7'),
 ('M6E', 'EUR'),
 ('NIY', 'NKD'),
 ('NKD', 'NIY'),
 ('NQ', 'ES'),
 ('RTY', 'EMD')]

我想从中创建一个列表列表，将至少出现一次的符号聚集在一起。

例如 ('CHF', 'EUR') 和 ('E7', 'EUR') 将合并到 1 个列表 ['CHF '、'EUR'、'E7'] 等等。

知道如何实现这一目标吗？

<小时/>

对于那些询问的人，这里是执行此操作的循环想法:

groups=[[]]
for item in li:
    for group in groups:
        if item[0] in group or item[1] in group:
            group.append(item)
        else:
            groups.append([item])

非常慢而且丑陋 - 实际上它的内存使用量让我的机器震惊了。

预期结果为[{'AUD', 'M6A'}, {'CHF', 'E7', 'EUR', 'M6E'}, {'EMD', 'ES', 'NQ ', 'RTY'}, {'GBP', 'M6B'}, {'GF', 'LE'}, {'NIY', 'NKD'}]

Answer 1

您正在寻找不相交的图，可以使用 networkx 来解决:

In []:
import networkx as nx
edges = [('AUD', 'M6A'), ('CHF', 'E7'), ('CHF', 'EUR'), ...]
g = nx.Graph(edges)
list(nx.connected_components(g))

Out[]:
[{'AUD', 'M6A'},
 {'CHF', 'E7', 'EUR', 'M6E'},
 {'EMD', 'ES', 'NQ', 'RTY'},
 {'GBP', 'M6B'},
 {'GF', 'LE'},
 {'NIY', 'NKD'}]

​如果您想避免使用 networkx 您可以自己合理有效地编写它(这应该是 O(n) 来创建图形和 O( n) 创建不相交的集合 - 总体来说是 O(n)) 例如:

In []:
g = {}
for a, b in edges:
    g.setdefault(a, []).append(b)
    g.setdefault(b, []).append(a)

r = []
while g:
    s = set()
    q = [next(iter(g))]
    while q:
        k = q.pop()
        if k in s:
            continue
        s.add(k)
        for e in g.pop(k):
            q.append(e)
    r.append(s)
r

Out[]:
[{'AUD', 'M6A'},
 {'CHF', 'E7', 'EUR', 'M6E'},
 {'EMD', 'ES', 'NQ', 'RTY'},
 {'GBP', 'M6B'},
 {'GF', 'LE'},
 {'NIY', 'NKD'}]