元素在列表列表中的出现

Question

假设我有一个列表

 record = [['g1','g2','g3'],['g2','g4'],['g1','g3','g5'],['g2','g3','g5'],['g1','g4']]

我有一个元组列表

list1 = [('g1','g2'),('g1','g3'),('g1','g4'),('g1','g5'),('g2','g3'),('g2','g4'),('g2','g5'),('g3','g4'),('g3','g5'),('g4','g5')]

现在记录中有多少次('g1','g2')？ 解应该是1，因为('g1','g2')只存在于['g1','g2','g3']

我可以将元组列表更改为列表列表。有什么方法比暴力更简单吗？因为我的列表可能包含10万个项目

Answer 1

将列表列表中的项g1, g2, ...视为无向图的顶点。浏览你的列表并建立图表。每当g1和g2出现在同一子列表中时，将g1 <-> g2的权重增加1。然后，您要查找的数字是元组元素上的边事件的权重。你知道吗

这假设元组总是有两个元素。如果元组是任意大小的，除了子表是任意的，那么这个问题就归结为寻找多个子图同构，每个子图同构都是NP完全的。看这个：https://stackoverflow.com/a/5279581/1749870

Answer 2

虽然不漂亮，但很管用：

record = [['g1','g2','g3'],['g2','g4'],['g1','g3','g5'],['g2','g3','g5'],['g1','g4']]
pattern = [('g1','g2'),('g1','g3'),('g1','g4'),('g1','g5'),('g2','g3'),('g2','g4'),('g2','g5'),('g3','g4'),('g3','g5'),('g4','g5')]

res = {}
for p in pattern:
    res[str(p)] = 0
    for r in record:
        if set(p).issubset(set(r)):
            res[str(p)] += 1

print(res)

编辑：
10^6项？（好吧，那就不行了……）