如何找到最少量的常见集

Question

鉴于集合

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

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

由于这是最短的集合列表,其中:

真实数据是一堆引用,而不是值类型.

编辑:我不认为总结我尝试过的东西可以帮助解决这个问题,并且只是为了分散注意力,因为类别理论中可能有一个算法,但是(出于娱乐原因)这里有:

Answer 1

首先,让我们仔细描述您的问题.

一个关系是一个函数有两个参数,并返回一个布尔值,指示关系是否成立.例如,"小于"是一种关系.

一种等价关系是一种关系是自反的 -每一个项目是关系到自身- 对称 -和-如果A到B,那么B是关系到一个相关的传递 -如果是涉及到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}这种关系不成立.

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

合理？

一旦你弄清楚了这个算法,有许多方法可以优化它.先把它弄好.

注意我在这里做了什么:我通过解决等价分区的一般问题解决了你的具体问题.如果您对如何编写本文很聪明,那么您将能够重用逻辑来解决任何等价分区问题,而不仅仅是您的具体问题.