[python] どう書く？-- 一方向リスト編

今日の御題。

a は b を参照し、b は c を参照し、c は d を参照し・・・ という、いわゆる一方向リストがある。 このデータ構造体における終端のオブジェクトを返す関数を書け

わたしはこれを「a を指定すると b が返り、b を指定すると c が返り、c を指定すると d が返る・・・」 というデータ構造体と考え、これは Python では辞書で表現できると考えた。そこで書いた答えが↓

# coding: utf-8
def get_endpoint( linked_list ):
	"""
	循環リストの場合は None を返す。
	線形リストの場合は終端のオブジェクトを返す。
	"""
	if (set( linked_list.keys() ) ^ set( linked_list.values() )) == set([]):
		return None
	
	difference = set( linked_list.values() ) - set( linked_list.keys() )
	return (difference if difference else None)

最後の2行はもともとは return (set( linked_list.values() ) - set( linked_list.keys() )) だったんだけど、 それでは部分的に巡回するリストだった場合に空集合 φ が返ってしまうので上記のように修正を加えた。 それでも正しく動作しないという人がいるんだけど、わたしには正しく動作するように思える。

まず、一方向リストにはリングバッファ( 円形リスト ) と線形リストがある。このうち、リングバッファについては 集合 set( linked_list.keys() ) と集合 set( linked_list.values() ) の対象差は空集合φになるのは 考えるまでもなく明白である。

リングバッファを次のように表現しよう

circular_list = {a:b, b:c, c:d, d,a}

この場合、circular_list の鍵を要素としてもつ集合は set([a, b, c, d]) となり、 値を要素として持つ集合は set([b, c, d, a]) となる。両者の対象差は当然 φ になる。

そして部分的に循環がある場合は、値の集合から鍵の集合を引いた差 difference が φ になる。 difference が φ でないのは、終端が存在する一方向線形リストのときだけなのだ。

スタックを使った方が簡単だといわれたのだが、わたしにはそちらの方がよほど難しいように思える。 実際、集合を使ったアルゴリズムはすぐに思いついたけど ( 初版のコードはエラーあったけど( ´･ω･`) ), スタックを使ったコードはむしろ何でスタックが必要なのか理解に苦しんだ。 何より数学的に美しくないと感じるのだ。