分区的列表组通过共同元素

StackOverflow https://stackoverflow.com/questions/178913

  •  05-07-2019
  •  | 
  •  

题

这里的脸谱的问题：给予一个名单的设置，诸如：

[ (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) ] ]

注意stickeyness-set(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,但是我会很高兴的一般方向的解决方案。

编辑:改变表中列名(元件，set_id)代替(键组)，以使条款更加一致。注意，凯文的答复使用古老的列名。

有帮助吗？

解决方案

问题是完全计算的连接组成一个超图:在整数的顶点，并将集的hyperedges.一个通常的方式计算的连接组成部分是通过水淹了他们之后的其他：

  • 所有i=1到N，这样做：
  • 如果我已经被标记的一些j < 我，然后继续(我的意思是跳到下一个i)
  • 别flood_from(i，i)

在flood_from(i，j)将被定义为

  • 对于每个集S含有我，如果它是不是已经标记j则：
  • 标记S j并为每个元件k S，如果k未标记j，那么标记，由j，并呼吁flood_from(k,j)

标签的设置然后让你相连的部件。

在条款的数据库，算法可以表述如下：添加标签列的数据库，并计算的连接组成部分设置我这样做

  • S=选择的所有行set_id==我
  • 设置标签给我的行在S
  • S'=选择的所有行标记并不设定和在那里件是在件(S)
  • 同时S'不是空的，做
  • ----设置标签给我的行在S'
  • ----S"=选择的所有行标记并不设定和在那里件是在件(S')
  • ----S=S盟S'
  • ----S'=S"
  • 回set_id(S)

另一个(理论)方式提出这种算法，将是说你正在寻找的固定点映射：

  • 如果={了1,...，n}是一组组，定义联盟(一)=一个1 联盟...联盟的一个n
  • 如果K={k1,...,kp}是一套整体、发病率定义(K)=设定的设定相交K

然后如果S是一个设定、连接组成部分S获得通过循环(发生)o(联盟)在S直到一个固定点，达到：

  1. K=S
  2. K'=事件(联盟(K))。
  3. 如果K==K'，然后返回K，K=K'和去2.

其他提示

您可以将其视为一个图形问题，其中集合（1,2,3）通过2连接到集合（5,2,6）。然后使用标准算法来细化连接的子的曲线图。

这是一个快速的python实现：

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]

#first find the links
for n in range(len(nodes)):
    for item in nodes[n]:
        for m in range(n+1, len(nodes)):
            if (item in nodes[m]):
                links[n].add(m)
                links[m].add(n)

sets = []
nodes_not_in_a_set = range(len(nodes))

while len(nodes_not_in_a_set) > 0:
    nodes_to_explore = [nodes_not_in_a_set.pop()]
    current_set = set()
    while len(nodes_to_explore) > 0:
        current_node = nodes_to_explore.pop()
        current_set.add(current_node)
        if current_node in nodes_not_in_a_set:
            nodes_not_in_a_set.remove(current_node)
        for l in links[current_node]:
            if l not in current_set and l not in nodes_to_explore:
                nodes_to_explore.append(l)
    if len(current_set) > 0:
        sets.append(current_set)

for s in sets:
    print [nodes[n] for n in s]

输出：

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]

这可能效率很低，但它应该起作用，至少：从一个键开始，选择包含该键的所有组，选择这些组的所有键，选择包含这些键的所有组等，以及一旦步骤不添加新的键或组，您就有一个子图的所有组的列表。排除这些并从头开始重复，直到您没有数据为止。

就SQL而言，我认为这需要一个存储过程。 WITH RECURSIVE可能会以某种方式帮助你，但我还没有任何经验，我不确定它在你的数据库后端是否可用。

在考虑了这个之后，我想出了这个：

  1. 使用列groups
    2. 创建一个名为(group_id, set_id)的表
  2. 按sets对element表格进行排序。现在应该很容易找到重复的元素。
  3. 遍历sets表，当你找到一个重复的元素时：
    1. 如果set_id表中存在group_id字段之一，则添加另一个具有相同<=>的字段。
    2. 如果<=>表中不存在<=>，则生成新的组ID，并将<=>添加到<=>表中。

    4. 最后，我应该有一个包含所有集合的<=>表。

    这不是纯粹的SQL，但看起来像O（nlogn），所以我想我可以忍受。

    马特的回答似乎更正确，但我不确定如何在我的情况下实现它。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top