如何找出最小数量的公共集合

Question

给定的集合

{1,2,3,4} {2,3,4} {1,4}

查找组的简单算法(最好是执行算法)是什么：{1} {2,3} {4}

由于这是最短的集合列表，因此：

• 所有成员(1-4名)都派代表出席。
• 2和3被分组在一起，因为它们总是出现在原来的集合中。

真正的数据是一堆引用，而不是值类型。

编辑:我不认为总结一下我尝试过的东西可以帮助这个问题，只会分散注意力，因为在分类理论中可能有这样的算法，但是(出于娱乐的原因)下面是这样说的：

• 我聚集在哈希集上，试图使用联合运算符。
• 我在gethashcode的集合上做过歌迷表演。
• 我使用第一个条目作为候选集合来迭代列表，试图在与其他成员进行比较时逐渐减少它。这并不是很好的表现，我也不确定它以最少数量的集合可能结束。

Answer 1

首先，让我们仔细描述一下您的问题。

关系是一个函数，它接受两个参数，并返回一个bool，指示该关系是否有效。例如，“小于”是一种关系。

等价关系是一种自反关系--每一项都与自身相关--对称--如果A与B相关，则B与1可传递--如果A与B相关，B与C相关，则A与C相关。

等价关系形成集合的等价划分，即每个子集中的每个元素相互关联的若干子集。每个子集被称为等价类。例如，整数"A“和”B“上的等价关系是相关的，如果它们的差可被3整除，则构成三个等价类：

{0, 3, -3, 6, -6, ... }
{1, 4, -2, 7, -5, ... }
{2, 5, -1, 8, -4, ... }

你希望组成你所有的集合的联盟：

{1, 2, 3, 4} U {2, 3, 4} U {1, 4} U {1} --> {1, 2, 3, 4}

然后将集合划分为等价类，其中等价关系是"A和B是相关的当且仅当A和B总是出现在每个原始集合中“。

首先，形成一个字典，将每个元素映射到其关联的等效类。正如您正确地指出的，最坏的情况是，我们有等效分区，其中每个等效类只包含一个元素，所以让我们从它开始。(顺便说一句，这是"A等于B“等价关系的等效划分。)

1 --> { 1 }
2 --> { 2 }
3 --> { 3 }
4 --> { 4 }

现在从联合中生成所有无序对的集合：

{ {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} }

现在，对于每个无序对，问一个问题：“这个关系对这对有效吗？”

对于{1, 2}、{1, 3}、{1, 4}，这种关系不成立。

对于{2, 3}，该关系仍然有效，因此将2和3桶合并在一起：

1 -->     { 1 }
2 --\ 
     -->  { 2, 3 }
3 --/
4 -->     { 4 }

对于{2, 4}和{3, 4}，这种关系不成立。

现在，您完成了，并且从每个元素到其对应的等效类都有一个映射。

讲得通?

有许多方法可以优化这个算法，一旦你得到正确的。先纠正一下。

注意我在这里所做的工作:我通过解决等效分区的一般问题来解决您的具体问题。如果您对如何编写这个问题很聪明，那么您将能够重用逻辑来解决任何等价分区问题，而不仅仅是您的特定问题。

Answer 2

这里有一种方法得到了与你相同的答案：

var sets = new [] { new [] {1,2,3,4}, new [] {2,3,4}, new [] {1,4}, new [] {1}};
var results = sets.SelectMany((x,i) => x.Select(y => new { y, i }))
                .GroupBy(x => x.y).Select(x => new { x.Key, g = string.Join("", x.Select(y => y.i).ToArray())})
                .GroupBy(x => x.g).Select(x => x.Select(y => y.Key).ToArray()).ToArray();

我可能会将这个查询的结果定义为可以用来组成原始集的最小集合的最短列表。它使用值的索引作为对它们进行分组的方法。(1出现在0，2，3中；4出现在0,1,2等中)2和3具有相同的索引数组，因此它们在最终结果中被分组。

我的第一种方法在集合{1,2,3,4}，{2,3,4}，{1,4} (答案应该是{1}，{4}，{2,3})时不能正确工作。这个会的。

Answer 3

虽然Eric正确地描述了解决方案，但我不知道如何为它创建好的并行代码。因此，我不得不采用这种办法。我的解决方案如下

{1,2,3,4} {2,3,4} {1,4} {1}

让我们分别调用对这些列表A、B、C和D的引用。

A :{1,2,3,4}
B: {2,3,4}
C: {1,4}
D: {1}

我执行了SelectMany，将每个成员与来自它的列表的引用关联起来。

A, 1
A, 2
A, 3
A, 4
B, 2
B, 3
B, 4
C, 1
C, 4
D, 1

然后我把他们按会员分组。

1 : {A,C,D}
2 : {A,B}
3 : {A,B}
4 : {A,B,C}

(这里我们看到，2和3有类似的列表，因为它们出现在相同的原始列表中)。这也是关键。

为了找到具有相同成员的列表，我通过XOR-对列表项的GetHashcode()结果进行了聚合()。所以对于"1"，我实际上做到了

var SomeInt = A.GetHashcode()^C.GetHashcode()^D.GetHashcode().

从而为每个成员生成一个int。

1: SomeIntA
2: SomeIntB
3: SomeIntB
4: SomeIntC.

在这上面分组。我终于得到了我想要的。{1}，{2,3}，{4}