我有一组由 Data.Set
中的 Set (Set a)
类型表示的集合.
我想联合所有交集不为空的成员集。
同样,如果 x 和 y 在同一个 Set 中。
示例:
-- import qualified Data.Set as S
ghci> f $ S.fromList [S.fromList [1,2], S.fromList [2,3], S.fromList [5]]
> S.fromList [S.fromList [1,2,3], S.fromList [5]]
ghci> f $ S.fromList [ S.fromList [1,2], S.fromList [2,3], S.fromList [3,4] ]
> S.fromlist [ S.fromList [1,2,3,4] ]
什么是优雅且性能的解决方案?
最佳答案
对于要合并的大量集合,您要使用 union find算法。
您可以在此处找到实现联合查找算法的 Haskell 代码:
https://github.com/erantapaa/union-find-example
此外,对于 Int 集,您需要使用 Data.IntSet
- 它效率更高。
之前我写了以下不传递合并集合的内容:
这是一个折叠:
import qualified Data.Set as S
import Data.List (foldl')
mergeSets as = foldl' merge [] as
-- merge one set into a list of sets
merge [] a = [a]
merge (b:bs) a = if S.null (S.intersection a b)
then b : merge bs a
else (S.union a b) : bs
test = mergeSets [ S.fromList [1,2], S.fromList [2,3], S.fromList [5] ]
关于haskell - 如何合并 Haskell 中的所有相交(Set a)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32122778/