【Java】アナグラムの生成ロジックの検証（「かとうあい」「あとうかい」のモンテカルロ法による実験）

IT

前回のつづき
自分で作ったアナグラム生成ロジックが
ほんとに正しく機能しているのか確かめるべく
暇つぶしついでに少し実験をしてみた。
実験内容は
「かとうあい」を入力としてアナグラム生成ロジックを適用した後、
「あとうかい」を得られる確率は理論値に近似するか
 というくだらないものである。

「かとうあい」と「あとうかい」がアナグラムの関係になっているのは
アナグラムに関して調べたときにWikipediaに載っていた事例であり
なぜか印象に残っているので使わせていただくが
これを採用したことにそれ以上の深い意味はまったくない。


 


実験用として以下プログラムを新たに用意する。
別にやってることは大したことなく、
先日のプログラムの入力に指定回数分延々と"かとうあい"を渡して
出力が"あとうかい"になった回数をカウントし、
最後に確率を計算するだけの簡素なプログラムである。

import java.text.*;  

public class AnagramTest1 {


private static final String INPUT_STR = "かとうあい";  
private static final String OUTPUT_STR = "あとうかい";  
private static final long TEST_COUNT = (long)10000000;  
private static final long LOG_COUNT = (long)(TEST_COUNT / 10);  

public static void main(String[] args) throws Throwable {  
  
	System.out.println("★開始");  
	  
	AnagramMake am = new AnagramMake();  
	long count = 0;  
	long collect = 0;  
	while (count < TEST_COUNT) {  
	  
		String output = am.makeAnagram(new String[]{INPUT_STR});  
		if (output.equals(OUTPUT_STR)) {  
			collect++;  
		}  
		count++;  
		if (count % LOG_COUNT == 0) {  
			System.out.println("【" + count + "】回ループしました...");  
		}  
	  
	}  
	  
	double kakuritu = (double)collect / (double)TEST_COUNT;  
	String kakurituStr = new DecimalFormat("0.00000").format(kakuritu);  
	System.out.println(OUTPUT_STR + "になった回数→【" + collect + "回】");  
	System.out.println(OUTPUT_STR + "の確率　　　　【" + kakurituStr + "】");  
	System.out.println("★終了");  
  
  
}  



}


ちなみに理論値の考察であるが、
「かとうあい」は５文字の文字列なので、
その並び替え方は5!=120通りある。
うち、「あとうかい」は１通りしかないので、確率は1/120＝0.008333…となる。

120回に1回は「あとうかい」になる計算なので、
1000回もやれば十分っぽい気もするが、
とりあえず10000000回（1千万回）を試行回数にしてみる。
（↑のプログラムはそうなってる）

以下、実験結果。

★開始  
【1000000】回ループしました...  
【2000000】回ループしました...  
【3000000】回ループしました...  
【4000000】回ループしました...  
【5000000】回ループしました...  
【6000000】回ループしました...  
【7000000】回ループしました...  
【8000000】回ループしました...  
【9000000】回ループしました...  
【10000000】回ループしました...  
あとうかいになった回数→【83111回】  
あとうかいの確率　　　　【0.00831】  
★終了


理論値に大分近い！
ちゃんと動いているようだ。



ちなみに、ひらがなではなくアルファベット（ascii文字）ならどうなるか？
すなわち
「katouai」を入力としてアナグラム生成ロジックを適用した後、
「atoukai」を得られる確率は理論値に近似するか
 である。

むしろ前回の記事に書いたように、
個人的に作成したもともとの主旨がそもそも入出力にひらがなを想定していないため、
入出力の検討パターンとしてはこっちのが妥当である。
果たしてどうなるか？

今回は入力がascii文字なので、前回のプログラムの仕様に従えば、
50%の確率で1文字1文字が大文字に変換される可能性がある。
"katouai"は7文字だが、この仕様のため、並び替えのパターン総数は単純に7!とならない。
また、"katouai"中に「a」が２文字存在する為、並び替えの総数としては6文字の並び替えと同じになる。
6文字のうち、1文字だけ大文字になるパターンは6C1＝6
6文字のうち、2文字だけ大文字になるパターンは6C2＝21
…
と計算すると総和が63となり、加えて
6文字のうち、0文字だけ大文字なる（全部小文字）のパターンは6C0＝1
となって、合計して64通りになる。
7文字の並び方それぞれにこの64通りの大文字小文字の混在パターンが存在するので、
全パターン総数は7!×64＝322560(32万52560通り)である。
よって理論値の確率は1/322560＝0.0000031001984…となる。
まあ32万程度なら1千万回試行すれば大体理論値に近い値が取れそうではあるが、
欲張って試行回数を1億回にして（つまり1千万回の10倍にして）試してみることにする。

これにより微妙にプログラムの変更がかかる。
入力と出力の文字列の変更は上述した通りであるが、
これに加えて試行回数と、
確率を計算した後のテキストフォーマット文字が変更になる（小数点以下を増やす）。

……  
	private static final String INPUT_STR = "katouai";  
	private static final String OUTPUT_STR = "atoukai";  
……  
	private static final long TEST_COUNT = (long)100000000;  
……  
		String kakurituStr = new DecimalFormat("0.000000000000000000").format(kakuritu);  
……


結果は以下の通りである。

★開始  
【10000000】回ループしました...  
【20000000】回ループしました...  
【30000000】回ループしました...  
【40000000】回ループしました...  
【50000000】回ループしました...  
【60000000】回ループしました...  
【70000000】回ループしました...  
【80000000】回ループしました...  
【90000000】回ループしました...  
【100000000】回ループしました...  
atoukaiになった回数→【315回】  
atoukaiの確率　　　　【0.000003150000000000】  
★終了

実験値のほうが理論値より若干大きいが、概ね理論値通りと言えよう。
判断方法が定性的ではないが、大体プログラムが正常に動いてることがわかったので
（少なくとも俺の中では納得できたのでｗ）これにて終了とする。
ありがとう、かとうあいさん、あとうかいさん