フロイドのサイクル・サーチ・アルゴリズムが特定のポインタ・インクリメント速度で失敗するのはなぜですか？

Question

は、次のリンクされたリストを検討してください。次のように

1->2->3->4->5->6->7->8->9->4->...->9->4..... 

上記のリストがループを有する：ホワイトボードにリンクされたリストを描画

[4->5->6->7->8->9->4] 

、私に、手動で異なるポインタ手順のためにそれを解決しようとしました、differenためのポインタを

(slow_pointer_increment, fast_pointer_increment)

ので

- ポインタが移動方法を見ます次のようにTの場合は、次のとおり

(1,2), (2,3), (1,3) 

増分の第二対 - （1,2）及び（2,3）がうまく働いたが、私はペア（1,3）を使用する場合、アルゴリズムはありませんこのペアで動作するようです。このアルゴリズムが実際に成立するためのステップをどれだけ増やす必要があるかに関するルールはありますか？

私は、より遅くて速いポインタのための様々なインクリメントステップを探しましたが、なぜこのリストのインクリメント（1,3）のために機能していないのかという単一の関連する答えが見つかりませんでした。

Answer 1

アルゴリズムは、ポインタ増分とサイクル長の差が共起する（すなわち、それらの最大公約数が1でなければならない）場合にのみ、任意の位置でサイクルを見つけることが保証される。

一般的に、これは増分の差が1でなければならないことを意味します（これは、他のすべての正の整数と相補的な唯一の正の整数です）。

(1,3)について、差は3-1=2であり、サイクル長は2、2と2は、このようなアルゴリズムは、サイクルを見つけることが保証されていないcoprimesないです。

---

これを理解する鍵は、少なくともポインタが今までに満たしているかどうかをチェックする目的のために、サイクル内で低速と高速のポインタのポジションだけ互いに相対的に重要、ということです。それは、これらの2つは同じと考えることができますされています（差は両方のための1である）

slow fast    slow fast 
    ↓ ↓     ↓ ↓ 
0→1→2→3→4→5→0  0→1→2→3→4→5→0 

だから我々はで、fastIncrement-slowIncrementの増分で移動slow残りの定数とfastの位置の観点で考えることができ問題を指摘すると、

どの位置から始めても、ある速度（モードサイクル長）で動く特定の位置に到達することはできますか？

あるいは、より一般的には：

我々はすべての位置、いくつかの速度（MODサイクル長）で移動に到達することはできますか？

速度とサイクルの長さが共起する場合にのみ当てはまります。

は、例えば、4の速度および長さ6のサイクルを見 - 0から始まる、我々が訪問 - GCD（4,6）= 2、我々は、すべての第二の要素を訪問することができ
0, 4, 8%6=2, 6%6=0, 4, 2, 0, ...を。
これを実行するには、上の例の（1,5）（difference = 4）の増分を検討し、ポインタが決して満たされないことを確認してください。

---

少なくとも私の知る限り、（1,2）増分はアルゴリズムの基本的な部分とみなされます。

異なる増分を使用すると（上記の制約に従って）機能する可能性がありますが、それは「公式」アルゴリズムから離れることになり、より多くの作業が必要になります（リンクされたリストへのポインタは繰り返し増分する必要があるため、一般的な場合に明確な利点を持たずに、1ステップで1より多くインクリメントすることはできません）。