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 のシーケンスで少なくとも同じ頻度で発生します。順序。関心のあるサフィックスの最小長はありますか?

これに関係なく、1 つのアイデアは、すべてのシーケンスを連結し、他のどこにも現れない異なる整数でそれらを分離し、線形時間でhttp://en.wikipedia.org/wiki/Suffix_arrayを計算することです。接尾辞配列を 1 回通過するだけで、任意の長さの最も一般的なサブシーケンスを見つけることができます。また、配列を区切る文字が個性的。( 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 に答える