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に依存していません。これらは別々のグループに配置できます。bt

リストをできるだけ多くの非依存グループに分割する必要があります。

各グループは、グループが依存するすべての文字のセットになります。非依存文字は1セットとなります。

上記の出力例は次のとおりです。

[
    ['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と、 2 つの要素を取り、それらのセットを 1 つのセットに結合するunionの2 つの操作をサポートします。

union-find データ構造を設定し、入力内の各サブリストについて、サブリストの各要素をサブリストの最初の要素と結合できます。これにより、独立した要素を結合することなく、すべての依存要素を効率的にグループ化できます。

ランクとパス圧縮によるユニオンを使用した素集合フォレストとしてのユニオン検索データ構造の標準実装では、ランタイムは基本的に入力のサイズに比例します。入力の逆アッカーマン関数の係数だけ遅くなります。これは、実際のすべての入力サイズに対して本質的に一定です。

于 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

これを行う1つの方法を次に示します(再帰アルゴリズムを使用):

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 に答える