1

形式のタプルのリストがあります[(A,B),(B,A),(D,C),(E,F),(C,D),(F,E)]。だけのリストを返すにはどうすればよい[(A,B),(C,D),(E,F)]ですか? 私が見つけた唯一の解決策は、繰り返されるタプルを削除することであり、私が考えることができる唯一の解決策は、単純な O(n^2) ソリューションです。これを効率的に行う方法はありますか?

4

1 に答える 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 に答える