python - 制定依赖组

Question

使用下面的函数我可以生成一些测试数据。

import random, string
a = list(string.ascii_lowercase)
def gen_test_data():
    s = []
    for i in xrange(15):
        p = random.randint(1,3)
        xs = [random.choice(a) for i in xrange(p)]
        s.append(xs)
    return s

这是我的测试数据。

[
    ['a', 's'],
    ['f', 'c'],
    ['w', 'z'],
    ['z', 'p'],
    ['z', 'u', 'g'],
    ['v', 'q', 'w'],
    ['y', 'w'],
    ['d', 'x', 'i'],
    ['l', 'f', 's'],
    ['z', 'g'],
    ['h', 'x', 'k'],
    ['b'],
    ['t'],
    ['s', 'd', 'c'],
    ['s', 'w', 'd']
]

如果一个字母与另一个字母共享列表，则它依赖于该字母，并且任何字母都依赖于其他依赖项。例如

x 依赖于 ['a','c','d','g','f','i','h','k', 'l','q','p','s','u','w','v','y','x','z']

这些依赖也是双向的。 k 依赖于一切，包括 x

但是 x 不依赖于 b 或 t。这些可以放在不同的组中。

我需要将列表分成尽可能多的非依赖组。

每个组都是该组所依赖的所有字母的集合。非依赖字母将是一组。

上面的示例输出是

[
    ['t'],
    ['b'],
    ['a','c','d','g','f','i','h','k','l','q','p','s','u','w','v','y', 'x','z']
]

我正在尝试编写一个函数来执行此操作，但无法找到正确分组所有内容的正确方法。

Answer 1

这是经典connected components问题。有许多有效的线性时间或近线性时间算法可以解决它，例如深度优先搜索等图搜索算法或联合查找数据结构。

---

对于基于搜索的算法，您可以根据输入设置一个图，输入子列表中的节点相连，然后运行图搜索以查找哪些节点可以相互访问。图库，如 NetworkX可以为您处理大部分实现，或者您可以自己编写。例如，

import collections

def build_graph(data):
    graph = collections.defaultdict(list)
    for sublist in data:
        # It's enough to connect each sublist element to the first element.
        # No need to connect each sublist element to each other sublist element.
        for item in sublist[1:]:
            graph[sublist[0]].append(item)
            graph[item].append(sublist[0])
        if len(sublist) == 1:
            # Make sure we add nodes even if they don't have edges.
            graph.setdefault(sublist[0], [])
    return graph

def dfs_connected_component(graph, node):
    frontier = [node]
    visited = set()
    while frontier:
        frontier_node = frontier.pop()
        if frontier_node in visited:
            continue
        visited.add(frontier_node)
        frontier.extend(graph[frontier_node])
    return visited

def dependent_groups(data):
    graph = build_graph(data)
    components = []
    nodes_with_component_known = set()
    for node in graph:
        if node in nodes_with_component_known:
            continue
        component = dfs_connected_component(graph, node)
        components.append(component)
        nodes_with_component_known.update(component)
    return components

这将使运行时间与输入大小成线性关系。

---

你也可以使用 union-find data structure .联合查找数据结构将项目与集合相关联，每个集合由一个代表性元素表示。它们支持两种操作:find，它找到一个元素的代表；union，它接受两个元素并将它们的集合合并为一个集合。

您可以设置联合查找数据结构，并针对输入中的每个子列表，将子列表的每个元素与子列表的第一个元素合并。这将有效地对所有依赖元素进行分组，而无需将任何独立元素连接在一起。

通过联合查找数据结构的标准实现作为具有按等级联合和路径压缩的不相交集森林，运行时在输入大小上基本上是线性的。它会慢一倍 inverse Ackermann function输入的大小，对于所有实际输入大小基本不变。