2

我有 N 组值，例如。

  • S1 = {A,B,C,D,E}
  • S2 = {A,B,C,D,E,F}
  • S3 = {A,B}
  • S4 = {C,E,F,G,H}

我想知道每组集合中是否有不同或独特的价值......即。是否存在通过集合的“路径”，在每个集合中至少留下一个值，而不是在任何其他集合中。上面示例的答案将是 TRUE，因为您可能有：B 来自 S1，D 来自 S2，A 来自S3 和 S4 中的 C

一个错误的例子是：

  • S1 = {A,B,C}
  • S2 = {A}
  • S3 = {A,B}
  • S4 = {A,C}

因为值需要在集合之间复制。

与往常一样，我确信这个问题必须有一个简单的解决方案。任何帮助将不胜感激。谢谢

澄清

感谢到目前为止的答案，但我仍然对此感到有些困惑，尽管有什么（我认为）是一个简单的要求。我怀疑我让这个问题听起来比它实际代表的问题更令人困惑。

为了澄清，我的最终目标是：

  • 每组有一个值。
  • 这个新值列表应该彼此不同。
  • 从每组中选取的值是相对任意的。
  • 如果无法从输入集中导出单个不同的值，则该过程不应返回任何内容

我已经阅读了二分图和最大流量，但我看不到“树上的木头”最终我需要在 .NET 中编写一些代码来实现这一点，所以一些伪代码将是一个非常大的帮助，如果那是不可能的只是一个简单的相关算法的例子就很好了。

4

3 回答 3

3

用 ; 创建一个二分图

Set X containing value of nodes = {S1,S2,S3,...,SN}
Set Y containing value of nodes = {A,B,C...}

通过根据问题中给出的集合制作边，将此图与问题陈述相匹配。

问题归结为检查 X 和 Y 之间的“最大（二分）匹配”是否等于 N。如果需要知道值的分配，则也打印此匹配。

编辑（更多解释）

在此处输入图像描述

两个集合之间的边表示原始集合。我们需要找到边，使得 X 中的所有顶点都被覆盖并且没有 2 条边共享一个公共顶点

注意：可能存在多个最大匹配

于 2012-09-02T21:07:33.090 回答
1

我认为你的要求是这样的：

调用集合S1, S2, ..., Sn. 调用元素a1, a2, ..., am. 然后你想：

  • 对于每一个S，选择一个这样的成员，a至少S有一个S不包含那个a

所以在你的例子中：

  • S1 选择 B（不在 中S4）
  • S2 选择 D（不在 中S3）
  • S3 选择 A（不在 中S4）
  • S4 选择 C（不在 中S3）

为了解决这个问题，一种可能的方法是：

  • 遍历Ss 和 member as，跟踪所有不同a的 s 以及S它们出现的数量
  • 再次遍历Ss，对于每一个，查看a计数小于sn的总数的成员的构造计数列表S。选择a满足此要求的任意一个

我们完成了。

您的评论似乎有一个额外的要求“如果'A'存在于多个集合中，那么'A'应该留在其中一个集合中”，即

  • 对于每a一个是多个成员的S，那a就是一些的'挑选'成员S

但是，我看不出如何将您的评论与在您的示例中E存在多个S但从未被选中的事实相提并论。

于 2012-09-03T10:38:45.290 回答
0

让我们以表格的形式表示您的第一个示例中的数据：

    a   b   c   d   e   f   g   h
s1  .   .   .   .   .
s2  .   .   .   .   .   .
s3  .   .
s4          .       .   .   .   .

现在，我们正在寻找一些解决方案，例如这个（取自问题）：

s1=b, s2=d, s3=a, s4=c

标记的解决方案（一列中不能有两个 X）：

    a   b   c   d   e   f   g   h
s1  .   X   .   .   .
s2  .   .   .   X   .   .
s3  X   .
s4          X       .   .   .   .

这类似于在分配问题中为处理器选择任务......

但是，如果您不关心复杂性，那么检查所有可能的配置怎么样？

for (every element in s1) as e1
    for (every element in s2) as e2
        for (every element in s3) as e3
            for (every element in s4) as e4
                if (e1 != e2 != e3 != e4)
                    return true;
return false;

这是具有复杂性的微不足道的蛮力O(s1.length * s2.length * s3.length * s4.length)。

于 2012-09-02T20:15:59.490 回答