python - 给定一个字符串列表列表，找到最常见的字符串对，第二个最常见的对，.....，然后是最常见的字符串三元组，等等

Question

我有一个包含 k 个字符串列表的列表(这 k 个列表中的每一个都没有任何重复的字符串)。我们知道所有可能字符串的并集(假设我们有 n 个唯一的字符串)。

我们需要找到的是:最频繁的字符串对是什么(即，哪 2 个字符串在 k 个列表中一起出现的次数最多？第二频繁的字符串对，第三频繁的字符串对，等。此外，我想知道最常见的字符串三元组、第二常见的字符串三元组等。

我能想到的唯一算法非常复杂，基本上是为了解决最常见的对，我会从 n 个字符串 (O(n^2)) 中枚举出所有可能的对，并且对于它们中的每一个，检查有多少列表 (O(k))，然后我将对结果进行排序以获得我需要的结果，因此我的总体复杂度是 O(n^2.x)，忽略最后一种。

关于时间方面更好的算法有什么想法吗？ (这有望适用于字符串的三元组和字符串的四元组等)？ Python 中的代码是最好的，但详细的伪代码(和数据结构，如果相关)或详细的总体思路也很好!

例如:如果

myList=[['AB', 'AC', 'ACC'], ['AB','ACC'],['ACC'],['AC','ACC'],['ACC','BB','AC']], 

然后配对问题的预期输出将是:'AC','ACC' 是最常见的配对，'AB','ACC' 是第二常见的配对。

Answer 1

您可以使用 combinations , Counter和 frozenset :

from itertools import combinations
from collections import Counter

combos = (combinations(i, r=2) for i in myList)
Counter(frozenset(i) for c in combos for i in c).most_common(2)

输出:

[(frozenset({'AC', 'ACC'}), 3), (frozenset({'AB', 'ACC'}), 2)]