削除するのではなく、含めるセットを見つけようとしました。このようなもの?
(1) 要素のリストとそれらが含まれる集合のインデックス
(2) 要素のみに現れる要素を持つ集合のインデックスで回答リストを準備する
(3) (1) からのマップをくまなく調べ、要素の集合インデックスがが回答リストにない場合、その要素が含まれる最小のセットのインデックスを回答に追加します。
Haskell コード:
import Data.List (nub, minimumBy, intersect)
sets = [["a","b","c","e"],["a","b","d"],["a","c","e"]]
lengths = map length sets
--List elements and the indexes of sets they are in
mapped = foldr map [] (nub . concat $ sets) where
map a b = comb (a,[]) sets 0 : b
comb result [] _ = result
comb (a,list) (x:xs) index | elem a x = comb (a,index:list) xs (index + 1)
| otherwise = comb (a,list) xs (index + 1)
--List indexes of sets that have elements that appear only in them
haveUnique = map (head . snd)
. filter (\(element,list) -> null . drop 1 $ list)
$ mapped
--Comb the map and if an element's set-index is not in the answer list,
--add to the answer the index of the smallest set that element is in.
answer = foldr comb haveUnique mapped where
comb (a,list) b
| not . null . intersect list $ b = b
| otherwise =
minimumBy (\setIndexA setIndexB ->
compare (lengths!!setIndexA) (lengths!!setIndexB)) list : b
出力:
*Main> sets
[["a","b","c","e"],["a","b","d"],["a","c","e"]]
*Main> mapped
[("a",[2,1,0]),("b",[1,0]),("c",[2,0]),("e",[2,0]),("d",[1])]
*Main> haveUnique
[1]
*Main> answer
[2,1]