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

# 漸化式 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