2

我有一个整数数组列表，其中每个数组都有一些排序的数字。在这里，我想根据所有数组找到最常见的整数序列组合。例如，如果数组列表如下

A1 - 1 2 3 5 7 8
A2 - 2 3 5 6 7
A3 - 3 5 7 9
A4 - 1 2 3 7 9
A5 - 3 5 7 10

这里

{3,5,7} - {A1,A3,A5}
{2,3}   - {A1,A2,A4}

因此，我们可以将 {3,5,7} 或 {2,3} 作为最常见的组合。

现在我使用的算法如下

找到一个集合与所有其他集合的交集。并存储结果集。如果结果集已经存在，则增加结果集。例如：查找以下所有内容的交集

A1 intersection A2 
A1 intersection A3
A1 intersection A4
A1 intersection A5
A2 intersection A3  
A2 intersection A4 
A2 intersection A5  
A3 intersection A4
A3 intersection A5  
A4 intersection A5

这里 A1 交点 A3 与 A3 交点 A5 相同，因此 set-{3,5,7} 出现可以设置为 2。类似地，可以确定每个结果集出现。

但是这个算法需要 O(n^2) 复杂度。假设每个集合都已排序，我很确定我们可以找到一个复杂度为 O(n) 的更好算法，但我无法写下来。任何人都可以为此建议一个 O(n) 算法。

4

2 回答 2

1

如果您有一个长度为 n 的序列，则其前缀的长度为 n-1 并且至少出现频率相同 - 退化的情况是最常见的字符，它是长度为 1 的序列，其出现频率至少与任何更长序列。您是否有感兴趣的最小后缀长度？

不管怎样，一个想法是连接所有序列，用其他地方没有的不同整数将它们分开，然后以线性时间计算http://en.wikipedia.org/wiki/Suffix_array。一次通过后缀数组应该允许您找到任何给定长度的最常见子序列 - 它不应该跨越两个不同数组之间的间隙，因为每个长度为 n 的序列都是唯一的，因为分隔数组的字符是独特的。（另见http://en.wikipedia.org/wiki/LCP_array）

于 2013-03-03T16:39:25.530 回答
0

Haskell 中的这个例子不扫描交叉点。相反，它列出了每个列表的子序列，并将它们聚合到由子序列索引的数组中。要查找最常出现的子序列，只需显示数组中最长的元素。过滤输出以显示大于长度 1 的子序列。输出是一个元组列表，显示子序列和出现子序列的列表的索引：

*Main> combFreq [[1,2,3,5,7,8],[2,3,5,6,7],[3,5,7,9],[1,2,3,7, 9],[3,5,7,10]]
[([3,5],[4,2,1,0]),([5,7],[4,2,0]),([ 3,5,7],[4,2,0]),([2,3],[3,1,0]),([7,9],[3,2]),([2, 3,5],[1,0]),([1,2,3],[3,0]),([1,2],[3,0])]

import Data.List
import qualified Data.Map as M
import Data.Function (on)

sInt xs = concat $ zipWith (\x y -> zip (subs x) (repeat y)) xs [0..]
  where subs = filter (not . null) . concatMap inits . tails

res xs = foldl' (\x y -> M.insertWith (++) (fst y) [snd y] x) M.empty (sInt xs)

combFreq xs = reverse $ sortBy (compare `on` (length . snd)) 
            . filter (not . null . drop 1 . snd)
            . filter (not . null . drop 1 . fst)
            . M.toList
            . res $ xs
于 2013-03-04T04:35:48.060 回答