Rubyで「フロイドの循環検出法」を実装

たまに使うことがあるので、作ったコードを記録しておく。またこの機会に、アルゴリズムの動作原理を自分なりにまとめて理解する。

Rubyのコード

# 漸化式 x_{n+1} = f(x_{n}) で与えられる列が循環を持つとき、
# 循環に入るまでの長さ l と循環の長さ m を測る
def find_cycle(x0, limit = nil, &f)
	# 循環検出の回数制限を設定（終端 nil または Float::INFINITY で無限）
	seq = 1..limit

	# step1: 循環を検出する
	x = y = x0
	k = seq.find { (x = f[x]) == (y = f[f[y]]) }
	raise "failed to detect a cycle" unless k

	# step2: 循環に入るまでの長さを測る
	x = x0
	l = (x == y) ? 0
	  : seq.find { (x = f[x]) == (y = f[y]) }

	# step3: 循環の長さを測る
	m = seq.find { (x = f[x]) == (y = f[f[y]]) }

	[l, m]
end

if $0 == __FILE__
	# テスト： x_{n+1} ≡ x_{n} * 2 (mod 360), x_{0} = 133
	l, m = find_cycle(133) { |x| x * 2 % 360 }
	p [l, m]

	# x_{l} == x_{l+m} （かつ x_{l-1} != x_{l+m-1} ）になるはず
	ary = (l + m).times.inject([133]) { |a, _| a << (a.last * 2 % 360) }
	ary.each_with_index { |x, i| puts "%3d %4d" % [i, x] }
end

アルゴリズムの仕組み

以下のグラフ（ l = 11, m = 8 ）の図で説明する。

循環節のノードを円形に配置し、非循環節はノードが揃うように「巻き付けて」いる。結果として m の倍数番目のノード（ 0, m, 2m ）は円の中心から見て同じ方向に並んでいる。

• step1: 循環を検出する
  • x と y は共にスタート地点（ノード 0 、値 x0 ）から始める
  • x は1つずつ、 y は2つずつ進める
    • x が1周してノード m に来れば y は2周してノード 2m に来る
    • このように、 x と y はノード 0 と同じ方向で必ず並ぶ
  • x が循環に入ればいつか必ず y が追いつき x == y になる
    • この位置はやはりノード 0 と同じ方向、つまり m の倍数
    • あくまで m の倍数であり、循環の長さ m そのものではない可能性があることに注意
• step2: 循環に入るまでの長さを測る
  • x だけスタート地点に戻し、 y はstep1終了時（循環節にある m の倍数のノード）から続ける
  • x も y も1つずつ進める
    • 円の中心から見て x と y は常に同じ方向にいて並走する
  • すると、循環に入った瞬間（ノード l ）で必ず x == y になる
• step3: 循環の長さを測る
  • x と y は共に循環の中（簡単なのはstep2終了時）から始める
  • x は1つずつ、 y は2つずつ進める
  • この場合、step1と異なり x がちょうど1周で必ず x == y になる

参考

• フロイドの循環検出法 - Wikipedia
• Rでフロイドの循環検出法を可視化する - Qiita