2

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

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不依赖于bor t。这些可以放在不同的组中。

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

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

上面的一个示例输出是

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

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

4

3 回答 3

2

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

对于基于搜索的算法，您将根据您的输入设置一个图形，连接输入子列表中的节点，然后运行图形搜索以查找哪些节点可以相互访问。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 数据结构将项目与集合相关联，每个集合由一个代表元素表示。它们支持两种操作：find，它找到一个元素的代表，以及union，它接受两个元素并将它们的集合连接成一个集合。

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

使用联合查找数据结构作为不相交集森林的标准实现，通过秩和路径压缩进行联合，运行时在输入大小上基本上是线性的。它会因输入的反阿克曼函数的一个因子而变慢，对于所有实际输入大小而言，该函数基本上是恒定的。

于 2016-08-01T17:13:48.183 回答
1

这些是图的连接组件，您可以使用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']
]
于 2016-08-01T17:22:46.447 回答
0

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

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'])
于 2016-08-01T17:27:37.913 回答