c# - 如何找到最少数量的公共(public)集

Question

给定集合

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

找到组的简单(最好是高性能)算法是什么:{1}{2,3}{4}

因为这是最短的集合列表，其中:

• 所有成员 (1-4) 都有代表。
• 2 和 3 归为一组，因为它们在原始集中总是一起出现。

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

编辑:我不认为总结我尝试过的内容对解决问题有任何帮助，而且只会分散注意力，因为类别理论中可能有一个算法可以解决这个问题，但是(出于娱乐原因)这里是:

• 我尝试使用联合运算符对哈希集进行聚合。
• 我已经在 gethashcode 上对聚合执行了 groupedby。
• 我使用第一个条目作为候选集遍历了列表，在与其他成员进行比较时试图逐渐减少它。这表现不佳，我不确定它最终会以尽可能少的组数结束。

Answer 1

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

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

等价关系是自反的关系——每个项目都与其自身相关——对称——如果A是相关的与 B 相关，则 B 与 A 相关——并且传递性——如果 A 与 B 相关，B 与 C 相关，则 A 与 C 相关。

等价关系构成集合的等价划分；也就是说，多个子集，其中每个子集中的每个元素都相互关联。每个子集称为一个等价类。例如，整数上的等价关系“如果A和B的差能被3整除，则A和B相关”形成三个等价类:

{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} 关系不成立。

现在你已经完成了，你有一个从每个元素到它对应的等价类的映射。

有道理吗？

一旦您确定正确，您可以通过多种方式优化该算法。先把它弄对。

请注意我在这里所做的事情:我通过解决等价划分的一般问题 解决了您的具体问题。如果您对如何编写此代码很聪明，您将能够重新使用逻辑来解决任何等价划分问题，而不仅仅是您的特定问题。