вхождение элемента в списке списков

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']

Я могу изменить список кортежей в список списков. Есть ли простой подход, а не грубая сила? потому что мой список списков может содержит элементы 1000K

Answer 1

Это не красиво, но это работает:

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) 

Edit:
10^6 пункты? (ну это не будет работать тогда ...)

Answer 2

Рассмотрите элементы в списке списков, g1, g2, ... как вершины неориентированного графа. Перейдите по списку списков и постройте график. Каждый раз, когда g1 и g2 происходят в том же перечне, увеличьте вес g1 <-> g2 на 1. Затем число, которое вы ищете, - это вес края, инцидентного элементам кортежа.

Это предполагает, что кортежи всегда будут иметь два элемента. Если кортежи имеют произвольный размер, в дополнение к произвольным спискам, то эта проблема сводится к нахождению множественных изоморфизмов подграфов, каждый из которых является NP-полным. См. Следующее: https://stackoverflow.com/a/5279581/1749870