最常存在的组合

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

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）算法。

来源

2013-03-03 Vineeth Mohan

'{3,5}'' ？四个元素很常见，这意味着'{3,5}'实际上是最常见的组合。 – 2013-03-03 17:53:10

@groovy - 由于{3,5}是{3,5,7}的子集，与{3,5}具有相同的出现次数，{3,5}被提升为{3,5,7} – 2013-03-04 16:11:05

{3,5}与{3,5,7}不具有相同的出现次数。 {3,5}出现在A1，A2，A3，A5中。 {3,5,7}发生在A1，A3，A5 – 2013-03-04 18:13:18

如果有长度为n的序列，则其前缀是长度的n-1和发生频率至少 - 一个退化情况是最常见的字符，这是发生至少为长度为1的序列往往是任何更长的序列。你有一个你感兴趣的最小后缀长度吗？

无论如何，一个想法是连接所有的序列，用不同的整数将它们分开，然后在线性时间内计算出http://en.wikipedia.org/wiki/Suffix_array。一次通过后缀数组应该让你发现任何给定长度的最常见的序列 - 它不应该越过两个不同的阵列之间的间隙，因为长度为n的每一个这样的序列是独特的，因为分离阵列中的字符是独特。（也见http://en.wikipedia.org/wiki/LCP_array）

来源

2013-03-03 16:39:25 mcdowella

我没有最小后缀长度。对任何长度超过一次的子集感兴趣。 – 2013-03-03 17:14:10

此示例在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 ，[（5,5]，[4,2,0]），（[3,5,7]，[0123] [4,2,0]），（[2,3]，[3,1,0]），（[7,9]，[3,2]），（[2,3,5]，[1 （0,1），（[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-04 04:35:48

最常存在的组合

回答

相关问题