给定一个字符串列表的列表，找到出现最频繁的两个字符串组合、第二频繁的组合......然后是出现最频繁的三个字符串组合等等。

Question

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

我们需要找到的是：哪两个字符串在k个列表中同时出现最多次（即最常见的一对字符串是哪两个？第二常见的一对字符串是哪两个？依此类推。此外，我还想知道最常见的三元组字符串、第二常见的三元组字符串等等。

我能够想到的唯一算法的时间复杂度很差，基本上为了解决最常见的一对，我会枚举所有可能的n个字符串中的每一对（O(n ^ 2))，然后检查它们在多少个列表中出现（O(k)），然后我会对结果进行排序以得到所需的内容，因此我总体的复杂度是O(n^2.x)，忽略最后一次排序。

有没有更好的时间复杂度算法的想法呢？（希望对三元组字符串和四元组字符串等也能运行良好）？用Python编写代码最好，但详细的伪代码（如果相关，则为数据结构）或详细的通用思路也可以！

例如：

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

那么，对于“pairs question”的期望输出应为：“AC”、“ACC”是最常见的一对，“AB”、“ACC”是第二常见的一对。

- Aly

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

- Mykola Zotko

---

如果这个答案包含相关的导入并参考前缀为 itertools.combinations 和 collections.Counter 的函数将会更有帮助。至于 frozenset，它是内置函数。 - Stef

@Stef 很好的提示。欢迎您编辑我的答案。 - Mykola Zotko

Answer 2

这是一个适用于所有组合长度的通用解决方案：

import itertools
def most_freq(myList, n):
    d={} #create a dictionary that will keep pair:frequency
    for i in myList:
        if len(i)>=n:
            for k in itertools.combinations(i, n): #generates all combinations of length n in i
                if k in d: #increases the frequency for this pair by 1
                    d[k]+=1
                else:
                    d[k]=1
    return {k: v for k, v in sorted(d.items(), key=lambda item: item[1], reverse=True)}  #this just sorts the dictionary based on the value, in descending order

例子：

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

>>> most_freq(myList,2)
{('AB', 'ACC'): 2, ('AC', 'ACC'): 2, ('AB', 'AC'): 1, ('ACC', 'BB'): 1, ('ACC', 'AC'): 1, ('BB', 'AC'): 1}
>>> most_freq(myList,3)
{('AB', 'AC', 'ACC'): 1, ('ACC', 'BB', 'AC'): 1}

- IoaTzimas

---

这种方法很完美，但是您能否更详细地为初学者和像我这样不太熟悉 lambda 函数的人逐步讲解它是如何工作的呢？非常感谢！ - Aly

Answer 3

我有一个相当简单的方法，不使用任何库。
首先，对于主列表中的每个列表，我们可以计算每对字符串的哈希值（更多关于字符串哈希的信息请参见：https://cp-algorithms.com/string/string-hashing.html）。维护一个字典，保存每个哈希出现的次数。最后，我们只需要对字典进行排序，以按其出现次数排序所有成对项。

例如：[['AB', 'AC', 'ACC', 'TR'], ['AB','ACC']]
对于列表1，即['AB', 'AC', 'ACC', 'TR']，
计算“AB AC”，“AC ACC”，“ACC TR”这些对的哈希值，并将它们相应地添加到字典中。对于主列表中的所有列表重复此操作。

- Abhinav Mathur

---

每个列表中的每对都需要一个哈希，你是什么意思？能再详细解释一下吗？另外，你能提供一些示例代码吗？非常感谢！ - Aly

Answer 4

在我的硬盘上找到了一段代码，请检查看它是否对你有帮助：

from collections import Counter
from itertools import combinations

mylist = [['AB', 'AC', 'ACC'], ['AB','ACC'],['ACC'],['AC','ACC'],['ACC','BB','AC']]
d  = Counter()
for s in mylist:
    if len(mylist) < 2:
        continue
    s.sort()
    for c in combinations(s,2):
        d[c] += 1

print(list(d.most_common()[0][0]))

将返回列表['AC'，'ACC']

- Wasif