6

一段时间以来，我一直在努力解决这个问题，但似乎我缺乏 Haskell 经验无法让我通过它。我在 Stackoverflow 上找不到类似的问题（其中大多数与合并所有子列表有关，没有任何条件）

就这样吧。假设我有一个这样的列表列表：

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

如果某种条件为真，是否有一种有效的方法来合并列表？假设我需要合并至少共享一个元素的列表。例如，结果将是：

[[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 中的 x，X 中的 y，xRy}。因此，对于您的示例，我们可能有 X 是一组列表， R 是“当且仅当 x 和 y 中至少有一个元素时 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]]

最明显的问题是我们得到了四个副本：两个来自将列表与其自身合并，两个来自“双向”合并列表。出现问题是因为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，因为Set不能作为实例Monad或Applicative由于其Ord约束。

我还注意到在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 回答