形式のタプルのリストがあります[(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)]
。だけのリストを返すにはどうすればよい[(A,B),(C,D),(E,F)]
ですか? 私が見つけた唯一の解決策は、繰り返されるタプルを削除することであり、私が考えることができる唯一の解決策は、単純な O(n^2) ソリューションです。これを効率的に行う方法はありますか?
1 に答える
5
ペアのコンポーネントのタイプが classOrd
にある場合、O(n log n) 時間で実行できます。
import Data.List (sort, group)
sortPair :: Ord a => (a, a) -> (a, a)
sortPair (x, y)
| x <= y = (x, y)
| otherwise = (y, x)
uniques :: Ord a => [(a, a)] -> [(a, a)]
uniques = map head . group . sort . map sortPair
したがって、定義すると
data T = A | B | C | D | E | F deriving (Eq, Ord, Show)
あなたの例のために、私たちは持っています:
> uniques [(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)]
[(A,B),(C,D),(E,F)]
于 2013-04-19T23:42:29.450 に答える