フロイドの循環検出法を学んだ

[ 7, 8, 9, 0, 1, 2, 0, 1, 2, 0, 1, 2・・・ ]

[ 10, 20, 30, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80,・・・]

のような数列があって、明らかに途中から繰り返しになっています。

繰り返しがどこから始まって、何個周期で繰り返しているのか検出したいときってあるじゃないですか。

いろいろググって「フロイドの循環検出法」というものがあるらしいということで、勉強しました。

紹介しているサイトはいくつかありますが、循環小数についての記事が大半で、ただの数列の循環検出に言及している記事が少なかったので、ここにメモしておきたいと思います。

意外にも、この QA サイトの質問者様のコードでかなり理解できました。
アルゴリズム - 数列の循環部分の探索について(47917)｜teratail

フロイドの循環検出法とは

超ざっくり説明します。

整数型の配列に数字が入っているとします。この配列のどこから循環が始まって、何個周期になっているのか調べます。

循環の開始位置を取得する

配列の要素を指す 2 つの変数（ A と B とします。）を用意し、いずれも最初の要素を指しておきます。

A は、2 つずつ数値を増やし、B は 1 つずつ数値を増やしてループします。

A と B の指す要素の値が一致した場合、A を最初の要素に戻し、今度は 1 つずつ数値を増やします。

再び A と B が指す要素の値が一致したときの A が循環の開始位置です。

循環の長さを取得する

そこからまた A は２つずつ値を増やします。次に A と B が指す要素が一致するまでの「ループの回数」が循環部分の長さです。

なぜこれで求められるかは、はっきり説明できません。（ｷﾘ

わかりやすい図が載っているサイトです。
Rでフロイドの循環検出法を可視化する

実際のプログラム

Java で組んでみました。

package org.yyama;

public class CirculationDetector {

	public static void main(String... args) {
		CirculationDetector _main = new CirculationDetector();
		_main.proc();
	}

	private void proc() {
		// 数列
		int[] arr = { 10, 20, 30, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80 };
		
		// 循環開始位置を取得
		int startPos = getStartPosition(arr);
		if (startPos == -1) {
			System.out.println("循環開始位置を検出できず。");
			return;
		}

		// 循環の長さを取得
		int cycle = getCycle(arr, startPos);
		if (cycle == -1) {
			System.out.println("循環の長さを検出できず。");
			return;
		}

		System.out.println("開始位置：" + startPos + " 循環部分の長さ：" + cycle);
	}

	/**
	 * 循環の開始位置を返します。
	 * 
	 * @param arr
	 *            数列
	 * 
	 * @return 循環開始位置。循環を検出できない場合は-1を返します。
	 */
	private int getStartPosition(int[] arr) {
		int a = 0;
		int b = 0;
		while (true) {
			a += 2;
			b++;
			if (a >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		a = 0;
		while (true) {
			a++;
			b++;
			if (b >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		return a;
	}

	/**
	 * 循環の長さを返します。
	 * 
	 * @param arr
	 *            数列
	 * @param startPos
	 *            循環の開始位置
	 * 
	 * @return 循環の長さを返します。循環を検出できなかった場合は-1を返します。
	 */
	private int getCycle(int[] arr, int startPos) {
		int cycle = 0;
		int a = startPos;
		int b = startPos;
		while (true) {
			cycle++;
			a += 2;
			b++;
			if (a >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		return cycle;
	}
}

実行結果はこちら。

開始位置：3 循環部分の長さ：4

たしかに合っていますね。

求められない場合もある

例えば先ほどの数列の 30 を 60 に変えると正しく動作しません。

		int[] arr = { 10, 20, 60, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80 };

結果がこちら。

開始位置：2 循環部分の長さ：2

循環している範囲の数値が循環前に現れると、正しく検出できないようです。

この弱点を克服するために、循環が３周現れたら「循環している」などと判断基準を厳しくすれば、より確度の高い循環検出処理となりそうです。

やってみましょう。

循環が複数回表れることを確認して「循環している」と判断するバージョン

かなりややこしくなってしまいましたが、できました。正しく検出できない数列も正しく検出できるようになりました。

まず、先ほどのやり方で循環開始位置候補と循環の長さ候補を求めます。本当にその候補が循環しているかどうか、3 周期チェックしています。

package org.yyama;

public class CirculationDetector {

	public static void main(String... args) {
		CirculationDetector _main = new CirculationDetector();
		_main.proc();
	}

	private void proc() {
		// 数列
		int[] arr = { 10, 20, 60, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80, 50, 60, 70, 80 };
		
		int startPos = 1;
		int tmpStartPos = -1;
		int cycle;

		do {
			startPos--;

			// 無限ループ防止用処理
			if (tmpStartPos == startPos) {
				startPos++;
			}
			tmpStartPos = startPos;

			// 循環開始位置を取得
			startPos = getStartPosition(arr, startPos);
			if (startPos == -1) {
				System.out.println("循環開始位置を検出できず。");
				return;
			}

			// 循環の長さを取得
			cycle = getCycle(arr, startPos);
			if (cycle == -1) {
				System.out.println("循環の長さを検出できず。");
				return;
			}
		} while (!isCirculating(arr, startPos, cycle, 3));

		System.out.println("開始位置：" + startPos + " 循環部分の長さ：" + cycle);

	}

	/**
	 * 循環の開始位置を返します。
	 * 
	 * @param arr
	 *            数列
	 * 
	 * @param tmpStartPos
	 *            この数値以降で循環を見つけます。
	 * 
	 * @return 循環開始位置。循環を検出できない場合は-1を返します。
	 */
	private int getStartPosition(int[] arr, int tmpStartPos) {
		int a = tmpStartPos;
		int b = tmpStartPos;
		while (true) {
			a += 2;
			b++;
			if (a >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		a = tmpStartPos;
		while (true) {
			a++;
			b++;
			if (b >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		return a;
	}

	/**
	 * 循環の長さを返します。
	 * 
	 * @param arr
	 *            数列
	 * @param startPos
	 *            循環の開始位置
	 * 
	 * @return 循環の長さを返します。循環を検出できなかった場合は-1を返します。
	 */
	private int getCycle(int[] arr, int startPos) {
		int cycle = 0;
		int a = startPos;
		int b = startPos;
		while (true) {
			cycle++;
			a += 2;
			b++;
			if (a >= arr.length) {
				return -1;
			}
			if (arr[a] == arr[b]) {
				break;
			}
		}
		return cycle;
	}

	/**
	 * 循環開始位置から、times回数循環しているかチェックします。
	 * 
	 * @param arr
	 *            数列
	 * @param startPos
	 *            循環開始位置
	 * @param cycle
	 *            循環の長さ
	 * @param times
	 *            何回繰り返したらOKか
	 * 
	 * @return true 循環していそう。 false 循環していない。
	 */
	private boolean isCirculating(int[] arr, int startPos, int cycle, int times) {
		// 循環していると思われる数列を作成
		int[] nums = new int[cycle];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = arr[startPos + i];
		}

		// 循環しているかチェック
		for (int i = 1; i < times; i++) {
			for (int j = 0; j < nums.length; j++) {
				if (startPos + (i * nums.length) + j >= arr.length) {
					return false;
				}
				if (arr[startPos + (i * nums.length) + j] != nums[j]) {
					return false;
				}
			}
		}
		return true;
	}
}

実行結果

開始位置：3 循環部分の長さ：4

ややこしいだけで、難しい処理はしていないので、じっくりステップ実行すれば、個々の処理の目的が分かると思います。

まぁこれでも１００％の循環検出はできないので、ご了承ください。

まとめ

循環検出難しい。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド