Algorithm to extract nodes of same class efficiently from a vector – StackOverflow
最も単純かつリーズナブルな方法は,無向グラフの接続コンポーネントを求める問題として捉えて,
import networkx as nx S = (2, 1, 1, 3, 6, 7, 5, 9, 6, 13, 12, 14, 12, 11) G = nx.Graph() G.add_edges_from(enumerate(S, 1)) pos = nx.spring_layout(G) nx.draw(G, pos, with_labels=True) list(nx.connected_components(G))
[{1, 2, 3, 4}, {5, 6, 7, 8, 9}, {10, 11, 12, 13, 14}]
基本的には,前からなぞっていけば解けるイメージなので,collections.defaultdict(set)を用いても簡単に解けそう.
from collections import defaultdict def groupby_edges(lst, g=0, sidx=1): dd = defaultdict(set) for i, x in enumerate(lst, sidx): j = lst[x-sidx] if i != 1 and x not in dd[g] and j not in dd[g]: g += 1 dd[g].update((i, j)) return dd S = (2, 1, 1, 3, 6, 7, 5, 9, 6, 13, 12, 14, 12, 11) groupby_edges(S)
defaultdict(set, {0: {1, 2, 3, 4}, 1: {5, 6, 7, 8, 9}, 2: {10, 11, 12, 13, 14}})