制定依赖组

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 的因素而变慢，这对于所有实际输入大小来说基本上是恒定的。

Answer 2

这些是图表的 connected components，您可以使用 networkx 生成它们：

>>> import networkx as nx
>>> graph = nx.Graph()
>>> for path in data:
...     nx.add_path(graph, path)
...
>>> [list(component) for component in nx.connected_components(graph)]
[
    ['h','q','c','d','a','g','p','f','s','w','i','v','u','x','z','y','k','l'],
    ['b'],
    ['t']
]

Answer 3

这是一种方法（使用递归算法）：

lst = [
    ['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']
]

def find_deps(letter, lst, already_done=set()):
    if letter in already_done:
        return already_done
    already_done = already_done.union(set([letter]))
    to_do = set()

    ## First scan the list to see what's there to process
    for sublist in lst:
        if letter in sublist:
            newset = set(x for x in sublist if x != letter)
            to_do = to_do.union(newset)

    ## Process first-dependents
    out = to_do.copy()
    for lll in to_do:
        out = out.union(find_deps(lll, lst, already_done=already_done))
    return out.union(set([letter]))

print find_deps('a', lst)
# set(['a', 'c', 'd', 'g', 'f', 'i', 'h', 'k', 'l', 'q', 'p', 's', 'u', 'w', 'v', 'y', 'x', 'z'])

print find_deps('b', lst)
# set(['b'])

print find_deps('t', lst)
# set(['t'])

制定依赖组

Working out dependent groups

python

graph-theory

connected-components