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

알고리즘의 작동 방식

참고