複数のタプルが含まれるリストから、リレーの順番のリストを作りたい

Question

以下のようなデータがあります。

STA = '山田'
b = [('鈴木','佐藤'),('山田','田中'),('田中','佐藤'),('渡辺','鈴木')]

このリストbは、バトンを渡すか渡される関係にある2人を表していて、
「山田は田中とペア、田中は佐藤とペア、佐藤は鈴木とペア、鈴木は渡辺とペア」
という関係が成り立っています。

このとき、STA(第1走者)である山田を起点として
R = ['山田','田中','佐藤','鈴木,'渡辺']
という「走る順」をリストの形で取り出すにはどうしたらよいでしょうか。

ただし、

• bは、複数個の「2つのデータが含まれるタプル」のみで構成される(3人組以上のペアは存在しない)
• 「渡す人が左側・渡される人が右側」とは限らない(「渡す人が右側・渡される人が左側」の場合もある)
• 「第1走者を含むタプル」は1つしかない
• 「最終走者を含むタプル」も1つしかない
• 途中でリレーが途切れることはない

とします。

なお、実際に扱うデータのbの要素数は上のように4個ではなく、もっと多く、100個くらいあります。

Answer 1

「渡す人が左側・渡される人が右側」とは限らない

という条件があるので、まずデータからグラフを作成し、始点のノード (今回の例だと山田) から順に辿っていけばいいのではないでしょうか？

networkx というライブラリを使用してます。(ない場合は pip install networkx)

import networkx as nx

pairs = [('鈴木', '佐藤'), ('山田', '田中'), ('田中', '佐藤'), ('渡辺', '鈴木')]
start = '山田'

G = nx.Graph()
G.add_edges_from(pairs)


# 深さ優先探索
print(list(nx.dfs_edges(G, source=start)))
# [('山田', '田中'), ('田中', '佐藤'), ('佐藤', '鈴木'), ('鈴木', '渡辺')]
# のようにエッジの情報が得られるので、

ret = [start] + [edge[1] for edge in nx.dfs_edges(G, source=start)]
print(ret)  # ['山田', '田中', '佐藤', '鈴木', '渡辺']

描画用コード (おまけ)

# Jupyter Notebook 上で実行
# graphviz 本体がインストールされている必要あり
from IPython.display import Image, display_png
A = nx.nx_agraph.to_agraph(G)
png = A.draw(format='png', prog='dot')
display_png(Image(png))

Comments

[koridentetsu]

ありがとうございます。無事できました！

Answer 2

すでに解決済みですが、Python の勉強がてら、愚直（愚鈍？）なバージョンを考えてみました。
（無駄なところを省きました。）

nodes = {}
runners = set()
for x, y in b:
    nodes.setdefault(x, []).append(y)
    nodes.setdefault(y, []).append(x)
    runners.add(x)
    runners.add(y)

baton_holder = sta
ans = [baton_holder]

for _ in range(len(runners)-1):
    runners.remove(baton_holder)
    candidates = nodes[baton_holder]
    for baton_holder in candidates:
        if baton_holder in runners:
            break
    ans.append(baton_holder)

print(ans)

hayataka2049 さんの回答を見て、「僕は、線形探索の回数を減らしたかっただけなんだよ。」と強がってみせる。

Answer 3

素直にループでやってみました。

STA = '山田'
b = [('鈴木','佐藤'),('山田','田中'),('田中','佐藤'),('渡辺','鈴木')]

x = STA
result = []
while b:
    result.append(x)
    for i, t in enumerate(b):
        if x in t:
            x = t[t[0] == x]
            break
    del b[i]
result.append(x)

print(result) # => ['山田', '田中', '佐藤', '鈴木', '渡辺']

Comments

[kts_h]

「x = t[t[0] == x]」
しびれました。