寻找重叠的集合

发布于 2024-09-25 16:12:54 字数 462 浏览 3 评论 0原文

我正在用 C# 编写一个数字喷泉系统。该系统的一部分为我创建了整数集，我需要找到创建的集合的组合可以让我留下一组只有一个项目的集合。最快的方法是什么？

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

我不需要找到所有组合，只要足以找到尽可能多的唯一数字即可。这可以用来创建更有效的算法。

我忘了提到的重要一点：我事先不知道有多少组，而是将它们逐一添加，并且每次都必须确定是否找到了我需要的每个数字。因此，该算法必须能够在添加新集合时分阶段运行。

铌。 C# 解决方案获得加分；)

原文

I'm writing a Digital Fountain system in C#. Part of this system creates me sets of integers, I need to find the combinations of sets which create can leave me with a set of just one item. What's the fastest way to do this?

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

I don't need to find all combinations, just enough to find me as many unique numbers as possible. This may be possible to exploit to create a more efficient algorithm.

An important point that I forgot to mention:
I do not know, beforehand, how many sets there are, instead I add them one by one, and must determine each time if I have found every number I require. So the algorithm must be something which can be run in stages as new sets are added.

Nb. Solutions in C# get bonus marks ;)

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

_畞蕅 2024-10-02 16:12:54

我认为通过使用贪婪集覆盖的某种修改可以获得一些不错的解决方案（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

编辑：

你可以在最后省略foreach循环
设置
这个只会给你带来一个
每组的解决方案（修复
这个你可以直接改变问题
进入集合覆盖问题并使用贪心
设置封面），例如如果您排列
[1,3,4]，你需要找到解决方案
其所有子集的 SCV 问题
大小 = 2: [1,3],
[1,4]，[3,4]。这会产生问题
您可能会考虑的更复杂的
另一种方式是
进化算法（表示
这里会很简单，对待
指定数字为位，适应度
函数应该变得更接近 1),
但这仍然没有解决问题
计算后添加新集合
（也许当你拥有最好的人口时
从上一个问题开始，然后添加后
新套装只需添加新位置即可
染色体）

i think some nice solutions can be gained by some sort of modification of using greedy set cover (http://en.wikipedia.org/wiki/Set_cover_problem) algorithm.

[pseudocode]
so:

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

edit:

you can ommit foreach loop for last
set
this will bring you no more than one
solution for each of sets (to fix
this you can change problem directly
into set cover problem and use greedy
set cover), for example if you array
[1,3,4], you need to find solution of
SCV problem for all subsets of it
that have size = 2: [1,3],
[1,4], [3,4]. it will make problem
much more complex
another way that you may consider are
evolution algorithms (representation
here will be very simple, treat
specified number as bit, fitness
function should grow closer to 1),
but this still don't solve problem of
adding new set after calculations
(maybe when you have best population
from last problem, then after adding
new set just add new place in
chromosome)