从元组列表中删除反转的重复项

Question

所以基本上我有一个元组列表[(a,b)],我必须从中做一些过滤.一个工作是删除反转的重复项,以便如果列表中存在(a,b)和(b,a),我只采用它们的一个实例.但列表理解并不是很有帮助.如何以有效的方式解决这个问题？

谢谢

Answer 1

也许一种有效的方法(O(n log(n)))将跟踪已经添加的元组(及其反转),使用Set:

import qualified Data.Set as Set                                                                                                                                                                        

removeDups' :: Ord a => [(a, a)] -> Set.Set (a, a) -> [(a, a)]
removeDups' [] _ = []
removeDups' ((a, b):tl) s | (a, b) `Set.member` s = removeDups' tl s
removeDups' ((a, b):tl) s | (b, a) `Set.member` s = removeDups' tl s
removeDups' ((a, b):tl) s = ((a, b):rest) where
    s' = Set.insert (a, b) s
    rest = removeDups' tl s'

removeDups :: Ord a => [(a, a)] -> [(a, a)]
removeDups l = removeDups' l (Set.fromList [])

该函数使用列表removeDups调用辅助函数removeDups',并使用空集调用.对于每一对,如果它或它的逆在集合中,则通过; 否则,添加它和它的反转,并处理尾部.\

复杂度为O(n log(n)),因为在每个步骤中,集合的大小在n中最多是线性的.

例

...

main = do
    putStrLn $ show $ removeDups [(1, 2), (1, 3), (2, 1)]

和

$ ghc ord.hs && ./ord
[1 of 1] Compiling Main             ( ord.hs, ord.o )
Linking ord ...
[(1,2),(1,3)]