6

しばらくの間、この問題に頭を悩ませようとしてきましたが、Haskell の経験が不足しているため、うまくいかないようです。ここ Stackoverflow で同様の質問を見つけることができませんでした (それらのほとんどは、条件なしですべてのサブリストをマージすることに関連しています)

それで、ここに行きます。次のようなリストのリストがあるとしましょう。

[[1, 2, 3], [3, 5, 6], [20, 21, 22]]

ある種の条件が真の場合、リストをマージする効率的な方法はありますか? 少なくとも 1 つの要素を共有するリストをマージする必要があるとしましょう。例の場合、結果は次のようになります。

[[1, 2, 3, 3, 5, 6], [20, 21, 22]]

別の例 (すべてのリストをマージできる場合):

[[1, 2], [2, 3], [3, 4]]

そしてそれは結果です：

[[1, 2, 2, 3, 3, 4]]

ご協力いただきありがとうございます！

4

2 に答える 2

4

効率性について何を言うべきかわかりませんが、何が起こっているのかを分析して、少なくともいくつかの異なる機能を得ることができます。特定の機能は最適化できる可能性がありますが、必要なものを正確に明確にすることが重要です。

質問を言い換えてみましょう:ある集合 X、ある二項関係 R、およびある二項演算 + について、集合 Q = {x+y | } を生成します。x in X、y in X、xRy}。したがって、あなたの例では、 X はリストのセットであり、 R は「 x と y の両方に少なくとも1つの要素がある場合に限り xRy 」であり、 + は++.

単純な実装では、set-builder 表記自体をコピーするだけかもしれません

shareElement :: Eq a => [a] -> [a] -> Bool
shareElement xs ys = or [x == y | x <- xs, y <- ys]

v1 :: (a -> a -> Bool) -> (a -> a -> b) -> [a] -> [b]
v1 (?) (<>) xs = [x <> y | x <- xs, y <- xs, x ? y]

その後p = v1 shareElement (++) :: Eq a => [[a]] -> [[a]]、あなたが望むものを達成するかもしれません。おそらくそうではないことを除いて。

Prelude> p [[1], [1]]
[[1,1],[1,1],[1,1],[1,1]]

最も明白な問題は、4 つのコピーを取得することです。2 つはリストをそれ自体とマージすることで、2 つはリストを相互に「両方向で」マージすることで作成されます。問題が発生するのListは、 が と同じではないため、一意のSetものを削除できないためです。もちろん、それは簡単な修正です。Setどこでも使用します

import Data.Set as Set

v2 :: (a -> a -> Bool) -> (a -> a -> b) -> Set.Set a -> Set.Set b
v2 (?) (<>) = Set.fromList . v1 (?) (<>) . Set.toList

もう一度試すことができp = v2 (shareElementますSet.toList) Set.union

Prelude Set> p $ Set.fromList $ map Set.fromList [[1,2], [2,1]]
fromList [fromList [1,2]]

これはうまくいくようです。のインスタンスにすることはできないListため、またはその制約のために、「通過」する必要があることに注意してください。SetMonadApplicativeOrd

には多くの失われた動作があることにも注意してくださいSet。たとえば、リスト内の注文情報を破棄するか、両方を処理する必要がx <> yありy <> x、関係が対称である場合に戦います。

いくつかのより便利なバージョンは次のように書くことができます

v3 :: Monoid a => (a -> a -> Bool) -> [a] -> [a]
v3 r = v2 r mappend

そして、関係がたとえば等式関係であると仮定すると、より効率的なものを構築できます。それ以来、O(n^2)操作を行う代わりに、関係の分割 (剰余類) の数でそれを行うことO(nd)ができます。d

一般的に、これは非常に興味深い問題です。

于 2013-05-09T15:48:47.523 に答える
2

たまたまここに似たようなことを書いた: Finding blocks in arrays

次のように変更できます (ただし、効率についてはよくわかりません)。

import Data.List (delete, intersect) 

example1 = [[1, 2, 3], [3, 5, 6], [20, 21, 22]]
example2 = [[1, 2], [2, 3], [3, 4]]

objects zs = map concat . solve zs $ [] where
  areConnected x y = not . null . intersect x $ y
  solve []     result = result
  solve (x:xs) result =
    let result' = solve' xs [x]
    in solve (foldr delete xs result') (result':result) where
  solve' xs result =
    let ys = filter (\y -> any (areConnected y) result) xs
    in if null ys 
          then result
          else solve' (foldr delete xs ys) (ys ++ result)

出力：

*Main> objects example1
[[20,21,22],[3,5,6,1,2,3]]

*Main> objects example2
[[3,4,2,3,1,2]]
于 2013-05-09T17:39:02.840 に答える