Найти частоту подмножеств среди множества множеств

Question

У меня есть следующий список навыков:

skills = ['Listening', 'Written_Expression','Clerical',
         'Night_Vision', 'Accounting']

У меня есть отдельный список наборов, каждый из которых содержит навыки, связанные с определенной работой:

job_skills =  
     [{'Listening','Written_Expression','Clerical','Night_Vision'},
     {'Chemistry','Written_Expression','Clerical','Listening'},
     .
     .
     ]

Я хочу посчитать частоту, с которой каждая комбинация из 2 уникальных навыков является подмножеством набора в job_skills, и вернуть список списков / наборов с комбинациями и частотами следующим образом:

skill_pairs = [{'Listening', 'Written_Expression', 2},
              {'Listening', 'Clerical', 2},
              .
              .
              {'Night_Vision', 'Accounting', 0}]

В данный моментЯ делаю следующее:

skill_combos = []
for idx, i in enumerate(skills):
    for jdx, j in enumerate(skills[idx+1:]):
        temp = []
        for job in range(len(job_skills)):
            temp.append(set([i,j]).issubset(job_skills[job])
        skill_combos.append([i,j,sum(temp)])

Это делает работу, но она медленная, учитывая, что у меня около полумиллиона комбинаций навыков. Есть ли более быстрый способ сделать это? В идеале не использовать 3 цикла.

Спасибо

Answer 1

Вам нужно только сосчитать имеющиеся комбинации, остальное равно нулю, например:

from collections import Counter
from itertools import combinations

job_skills = [{'Listening', 'Written_Expression', 'Clerical', 'Night_Vision'},
              {'Chemistry', 'Written_Expression', 'Clerical', 'Listening'}]


counts = Counter(combo for skill_set in job_skills for combo in combinations(skill_set, 2))

for key, value in counts.items():
    print(key, value)

Выход

('Clerical', 'Written_Expression') 2
('Clerical', 'Listening') 2
('Clerical', 'Night_Vision') 1
('Written_Expression', 'Listening') 2
('Written_Expression', 'Night_Vision') 1
('Listening', 'Night_Vision') 1
('Clerical', 'Chemistry') 1
('Written_Expression', 'Chemistry') 1
('Listening', 'Chemistry') 1

См. itertools.combinsk и collection.Counter . Если вам нужен словарь, который возвращает 0 для пропавших без вести, оберните counts defaultdict :

total = defaultdict(int)
total.update(counts)
print(total[('Night_Vision', 'Accounting')])

Вывод

0

Answer 2

Не уверен, что это быстрее, но вы можете использовать комбинации со счетчиком. Мое решение рассчитывает комбинации только один раз. Затем он использует запись issubset.

from itertools import combinations
from collections import Counter

skills = ['Listening', 'Written_Expression','Clerical',
         'Night_Vision', 'Accounting']
job_skills = [{'Listening','Written_Expression','Clerical','Night_Vision'}, {'Chemistry','Written_Expression','Clerical','Listening'}]

pairs = {frozenset(x) for x in combinations(skills, 2)}
c = Counter(pair for pair in pairs for job in job_skills if pair.issubset(job))

for pair in pairs: # Adding the pairs that had no matches
    if pair not in c:
        c[pair] = 0

for key, count in c.items():
    print(key, count)

Вывод:

frozenset({'Written_Expression', 'Clerical'}) 2
frozenset({'Listening', 'Clerical'}) 2
frozenset({'Written_Expression', 'Listening'}) 2
frozenset({'Written_Expression', 'Night_Vision'}) 1
frozenset({'Listening', 'Night_Vision'}) 1
frozenset({'Clerical', 'Night_Vision'}) 1
frozenset({'Written_Expression', 'Accounting'}) 0
frozenset({'Clerical', 'Accounting'}) 0
frozenset({'Listening', 'Accounting'}) 0
frozenset({'Night_Vision', 'Accounting'}) 0