7

[これが既知の問題に該当する場合はお知らせください]

さまざまなサイズの n セットがあります。セット内の各要素は一意です。また、各要素は、せいぜい 2 つの異なるセットで発生する可能性があります。

これらのセットに対して操作を実行したいが、要素の重複や欠落は避けたい。問題: これらの n 個のセットのうち、他のセットによってカバーされているため、どれを削除する必要があるかを調べます。

例 [a,b,c]; [a]; [b]。[a]、[b] はどちらも最初のもので覆われているため、削除します。

例 [a,b,c]; [a]; [b]; [CD]。[a,b,c] は 3 つの要素すべてが残りのセットでカバーされるため、削除します。注: ここで [a],[b] だけでは、「c」が重複しているため、有効な回答ではありません。同様に、[a]、[b]、[c、d] は有効な回答ではありません。削除すると「d」が失われるためです。

4

4 に答える 4

3

これは、 Tarjan のアルゴリズムに基づく方法を使用して線形時間で解決できる2-sat 問題のケースだと思います。

  1. 各セット i に対して変数 Ai を作成します。Ai は、セット i が含まれる場合にのみ真です。
  2. 単一のセットに現れる各要素に対して、Ai=1 という節を追加します
  3. 2 つの集合 i と j に現れる各要素について、節 (Ai && ~Aj) || を追加します。(~Ai && Aj)。これらの句は、Ai と Aj のいずれかが必ず出現する必要があることを意味していました。

標準の 2-sat アルゴリズムを使用してこれを解決し、これを達成することが不可能かどうか、または可能であれば満足のいく割り当てを見つけることができます。

V 個のセットと N 個の要素の場合、V 個の変数と最大 2N 個の句があるため、Tarjan のアルゴリズムの複雑さは O(V+2N) になります。

于 2013-05-31T08:54:17.167 に答える
0

削除するのではなく、含めるセットを見つけようとしました。このようなもの？

(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]
于 2013-06-01T13:58:44.243 に答える