algorithm - 查找一组中出现次数最多的数字组合

Question

这个问题与以下问题有关:

How to find most frequent combinations of numbers in a list

Most frequently occurring combinations

我的问题是:

场景:我有一组 numbers，EACH COMBINATION IS UNIQUE 并且组合中的每个数字只出现一次:

目标:查找此集合中组合(大小为 2)的出现频率。

例子:

频率阈值为2。

设置 = {1,12,13,134,135,235,2345,12345}

2个组合的度数为(显示出现次数超过2次的所有组合):

13 - appear 4 times

14 - appear 3 times

23 - appear 3 times

12 - appear 2 times

...

穷举搜索所有可能组合的时间复杂度呈指数级增长。

谁能帮我想出一种算法可以更快地解决这个问题？ (哈希表、异或、树搜索....)

谢谢

附言。不用担心空间复杂度

解决方案和结论:

templatetypedef 的答案适用于长度超过 3 的子串

如果子字符串的长度是2，btilly的答案很直接并且易于实现(在时间上也有很好的表现)

Answer 1

这是伪代码，其运行时间应该是 O(n * m * m) 其中 n 是集合的大小，m 是该集合中事物的大小:

let counts be a hash mapping a pair of characters to a count
foreach number N in list:
    foreach pair P of characters in N:
        if exists counts[P]:
            counts[P] = counts[P] + 1
        else:
            counts[P] = 1
 let final be an array of (pair, count)
 foreach P in keys of counts:
     if 1 < counts[P]:
         add (P, counts[P]) to final
 sort final according to the counts
 output final

如果您正在寻找 3、4 等字符的组合，@templatetypedef 的答案最终会更有效率。但这对于所述问题应该没问题。