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가 둘레로 노드 m에 오면 y는 둘레로 노드 2m에 온다

따라서 x와 y는 노드 0과 같은 방향으로 항상 정렬됩니다.

x 가 순환에 들어가면 언젠가 반드시 y 가 따라잡아 x == y

이 위치는 역시 노드 0 과 같은 방향, 즉 m 의 배수

어디까지나 m의 배수이며, 순환의 길이 m 그 자체가 아닐 가능성이 있는 것에 주의

step2: 순환에 들어갈 때까지의 길이를 측정한다

x 시작 지점으로 되돌아가고 y는 step1 종료시 (순환 절의 m의 배수 노드)에서 계속됩니다

x 도 y 도 하나씩 진행

원의 중심에서 보면 x 와 y 는 항상 같은 방향으로 병주한다

그러면 순환에 들어간 순간(노드 l)에서 반드시 x == y 가 된다

step3: 순환의 길이를 측정한다

x와 y는 모두 순환 중(간단한 것은 step2 종료시)로 시작한다

x 는 하나씩, y 는 2개씩 진행한다

이 경우 step1과 달리 x

참고

플로이드 순환 검출 방법 - Wikipedia

R에서 플로이드 순환 검출 방법 시각화 - Qiita