寻找重叠套

Question

我在写 数字喷泉 系统。该系统的一部分创造了我套整数，我需要找到该组合的设定创造可以离开我设的只是一个项目。什么是最快的方式这样做？

Set A: 1,2,3,4,5,6
Set B: 1,2,3,4,6
Set C: 1,2,3
Set D: 5,6

Solutions:
A - B => 5
A - (C + D) => 4

我不需要找到 所有 组合，刚够找到我的许多独特的号码成为可能。这可能可以利用以创造一个更有效率的算法。

很重要的一点，我忘了说了:我不知道，先，有多少套有，而不是我加入他们一个接一个，而且必须确定每个时候，如果我们发现每一个号码我需要的。这样的算法必须有一些可以运行阶段作为新加入。

Nb。方案C#获得奖励的标记；)

Answer 1

我认为一些很好的解决方案可获得了通过某种修改，使贪婪的设定涵盖(http://en.wikipedia.org/wiki/Set_cover_problem)的算法。

[伪] 所以：

1. sort sets by size descending
2.
foreach set in sets do:
  uncovered = set.size
  while uncovered > 1
    current_set = the biggest set that covers no more than (uncovered - 1) and was not used before to cover set
    uncovered = uncovered - covered_by_set(set)
    collect current_set to some array
  end
end

编辑：

• 你可以ommit foreach循环上 设置
• 这会给你带来不超过一个 每一个解决方案的设置(修复 这个你可以改变的问题直接 成套涵盖的问题和贪婪的使用 设定复盖)，例如如果你阵列 [1,3,4]，你需要找到解决办法的 法问题的所有集的子集 有大小=2:[1,3], [1,4],[3,4].它将使问题 复杂得多
• 另一种方式，可以考虑是 进化算法(代表 这将是非常简单，享 指定数量，作为位、健身 功能应该发展更密切1), 但是，这仍不能解决问题的 增加新的设置以后的计算 (也许当你有最好的人 从最后一个问题，然后后添加 新集只是增加新的地方 染色体)