Отработка зависимых групп

Это классическая проблема с связанными компонентами. Существует ряд эффективных алгоритмов с линейным или почти линейным временем для ее решения, например, с помощью алгоритма поиска по графу, такого как поиск в глубину, или с помощью структуры данных с объединением.

Для алгоритма, основанного на поиске, вы должны настроить граф на основе вашего ввода, с узлами во входных подсписках, связанных, а затем запустить поиск графа, чтобы найти, какие узлы достижимы друг от друга. Библиотеки графов, такие как 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, которая берет два элемента и объединяет их наборы в один набор.

Вы можете настроить структуру данных объединения-поиска и для каждого подсписка во входных данных объединить каждый элемент подсписка с первым элементом подсписка. Это позволит эффективно сгруппировать все зависимые элементы без объединения каких-либо независимых элементов вместе.

При стандартной реализации структуры данных объединения-поиска в виде леса непересекающихся множеств с объединением по рангу и сжатию пути среда выполнения будет по существу линейной по размеру входных данных. Это было бы медленнее в множитель обратной функции Аккермана ввода, которая по существу постоянный для всех практических входных размеров.

Это подключенные компоненты графика, и вы можете использовать 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']
]

Вот один из способов сделать это (используя рекурсивный алгоритм):

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