建立依赖组

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，用于获取两个元素并将其集合合并为一个集合。你知道吗

可以设置union find数据结构，对于输入中的每个子列表，将子列表的每个元素与子列表的第一个元素进行union。这将有效地将所有依赖元素分组，而不将任何独立元素连接在一起。你知道吗

对于union-find数据结构的标准实现，它是一个具有按秩合并和路径压缩的不相交集林，运行时的输入大小基本上是线性的。它会慢一点，慢一点的是输入的inverse Ackermann function，这对于所有实际的输入大小基本上都是不变的。你知道吗

Answer 2

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

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'])

Answer 3

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

>>> import networkx as nx
>>> g = nx.Graph()
>>> for node0, *nodes in test_data: 
...     g.add_node(node0) 
...     for node in nodes: 
...         g.add_edge(node0, node) 
... 
>>> for subgraph in nx.connected_component_subgraphs(g): 
...     print(subgraph.nodes) 
...
['a', 's', 'f', 'c', 'w', 'z', 'p', 'u', 'g', 'v', 'q', 'y', 'd', 'x', 'i', 'l', 'h', 'k']
['b']
['t']