7

[如果这与已知问题有关，请告诉我]

我有 n 套不同尺寸的。集合中的每个元素都是唯一的。每个元素最多可以出现在两个不同的集合中。

我想对这些集合执行操作，但要避免重复或丢失任何元素。问题：找出所有这些 n 个集合应该被删除，因为它们被其他集合覆盖。

例如 [a,b,c]; [一个]; [乙]。删除 [a], [b] 因为两者都被第一个覆盖。

例如 [a,b,c]; [一个]; [b]；[光盘]。删除 [a,b,c] 因为所有三个元素都被剩余的集合覆盖。注意：这里的 [a],[b] 单独不是有效的答案，因为 'c' 被复制。同样， [a],[b],[c,d] 不是有效答案，因为如果删除 'd' 将丢失。

4

4 回答 4

3

我认为这是Exact Cover 问题。最后一个约束——每个元素最多分为两组——在我看来并没有从根本上改变问题（尽管我很容易在这方面犯错）。维基百科网页包含各种算法方法的很好的总结。选择的算法似乎是Dancing Links。

于 2013-05-31T06:13:16.093 回答
3

我认为这是一个2-sat 问题的案例，可以使用基于Tarjan 算法的方法在线性时间内解决。

  1. 为每个集合 i 制作一个变量 Ai。当且仅当要包含集合 i 时，Ai 为真。
  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 回答
1

由于集合中的一个元素最多只能出现在两个集合中，那么集合之间存在相当直接的联系，可以用图表表示，两个例子如下所示。一个示例使用红线表示边缘，另一个示例使用黑线表示边缘。

图表示例

以上表明集合可以分为三组。

  1. 设置所有元素出现两次的位置。这些集合可能会被移除和/或包含这些元素的集合可能会被移除。
  2. 设置一个或多个元素出现两次的位置。出现两次的元素可能会链接到可以删除的集合。
  3. 设置没有元素出现两次。这些集合可以忽略。

目前还不清楚如果所有集合都在第 1 组或第 3 组中会发生什么。但是似乎有一个相当简单的标准可以快速删除集合，伪代码如下所示：

for each set in group2:
    for each element that appears twice in that set:
        if the other set that contains that element is in group1:
            remove the other set

然后，性能与元素数量呈线性关系。

于 2013-05-31T09:08:44.423 回答
0

我试图找到要包含而不是删除的集合。像这样的东西？

(1) 元素列表和它们所在的集合的索引
(2) 使用仅出现在其中的元素的集合的索引来填充答案列表
(3) 梳理 (1) 中的映射，如果元素的集合索引不在答案列表中，将元素所在的最小集合的索引添加到答案中。

哈斯克尔代码：

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 回答