按共享元素对集合列表进行分区
这是问题的关键：给定一组列表，例如：
[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ] 返回一组集合的列表，以使具有共享元素的集合在同一组中。
[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ] 请注意粘性-集（6,12,13）与（1,2,3）没有共享元素，但是由于（5,2,6）而将它们放在同一组中。
使事情变得复杂的是，我应该提到的是，我实际上并没有这些整洁的集合，而是一个具有几百万行的数据库表，如下所示：
element | set_id
1 | 1 2 | 1 3 | 1 5 | 2 2 | 2 6 | 2 等等。因此，我很乐意使用SQL来实现它，但是我对解决方案的总体方向感到满意。
编辑：将表列名称更改为（element，set_id）而不是（key，group_id），以使术语更加一致。请注意，Kev的答案使用了旧的列名。
问题来源于stack overflow
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
-
问题恰恰是超图连接部分的计算：整数是顶点，集合是超边。计算连接的组件的一种常用方法是依次将它们淹没：
对于所有i = 1到N，请执行以下操作： 如果我被j <i标记，则继续（我的意思是跳到下一个i） 否则Flood_from（i，i） 将Flood_from（i，j）定义为
对于每个包含i的集合S，如果尚未被j标记，则： 用j标记S，并为S的每个元素k标记k，如果k尚未用j标记，则用j标记它，然后调用Flood_from（k，j） 然后，集合的标签为您提供所需的已连接组件。
在数据库方面，该算法可以表示为：将TAG列添加到数据库中，然后通过执行以下操作来计算集合i的连接分量：
S =选择set_id == i的所有行 将S中的行的TAG设置为i S'=选择所有未设置TAG且元素在element（S）中的行 当S'不为空时， ----将S'中的行的TAG设置为i ---- S''=选择所有未设置TAG且元素位于element（S'）中的行 ---- S = S联合S' ---- S'= S'' 返回set_id（S） 表示此算法的另一种（理论）方式是说您正在寻找映射的固定点：
如果A = {A 1，...，A n }是一组集合，则定义union（A）= A 1 union ... union A n 如果K = {k 1，...，k p }是一组整数，则定义入射（K）=与K相交的一组集合 然后，如果S是集合，则通过对S迭代（入射）o（联合）直到达到固定点来获得S的连接分量：
K = S K'=发生率（联合（K））。 如果K == K'，则返回K，否则返回K = K'并转到2。
2019-11-18 17:26:49赞同 展开评论