無限の猿定理

2019-05-27プログラミング

こんにちは。今回も乱数関係の題材を取り上げます。今回は無限の猿定理をプログラムを作って実験してみます。

1. 無限の猿定理とは
2. そんなことならやってみようじゃないか（ひらがな編）
3. mojisuwo herashite miru（katakana編）

無限の猿定理とは

「猿がタイプライターの鍵盤をいつまでもランダムに叩き続ければ、シェークスピアの作品を打ち出す」ということから名前が付いた定理です。

これは比喩的な表現なので、猿がタイプすることを続けるか？または、ランダムにキーを叩くのか？はたまた、手をキーに置いたまま同じ文字が連続してしまうのか？猿にキーを打たせたことがないのでよくわかりませんが、ランダムな文字を作り続ければ、どんな文字列もいつかはできるということのようです。

そんなことならやってみようじゃないか（ひらがな編）

いつもはPythonでプログラムを書いていますが、とてもPythonの処理速度で結果が出そうにないので、今回はC++で書きます。

条件として、かな入力でひらがなを入力することにします。また、シェークスピアの大作を期待するのは無謀なので、松尾芭蕉の「古池や蛙飛びこむ水の音」の上五の「ふるいけや」と入力されるまでどれくらいの文字数を打ち続ければよいかを調べてみることにします。

そのプログラムは下にあるとおりです。猿が入力した文字を全部記録していたらとんでもない量の記憶容量が必要になるので、最後の数文字分だけ記憶しています。

#include <iostream>
#include <random>
using namespace std;

int main()
{
  string chars = "ぬふあうえおやゆよわほへーたていすかんなにらせ゛゜ちとしはきくまのりれけむつさそひこみもねるめろ";
  string goal = "ふるいけや";
  string tail = "";

  long long count = 0;

  random_device rnd;
  mt19937 mt(rnd());
  uniform_int_distribution<> rand_char(0, (chars.length() / 2) - 1);

  while (tail != goal)
  {
    int r = rand_char(mt);
    tail += chars[r * 2];
    tail += chars[r * 2 + 1];
    if (tail.length() > goal.length()) {
      tail = tail.substr(2, goal.length());
    }
    count++;
  }

  cout << count << "文字目" << endl;
  cout << tail << endl;
}

実行結果です。

75151249文字目
ふるいけや

179886394文字目
ふるいけや

219869379文字目
ふるいけや

たった５文字なのに・・・たった５文字なのに・・・よくて数千万回、だめだと二億回以上も入力しないと偶然入力できないんだ・・・

あまりにも実行時間が長いので３回しか実行できませんでした。

mojisuwo herashite miru（katakana編）

ほとんど変わっていませんが、文字をアルファベットとスペースだけにして、ローマ字入力にしたらどうか試してみます。とりあえず５文字目の「furui」までが正しく入力されるまでの文字数を数えるプログラムに変えてみます。

#include <iostream>
#include <random>
using namespace std;

int main()
{
  string chars = "abcdefghijklmnopqrstuvwxyz ";
  string goal = "furui";
  string tail = "";

  long long count = 0;

  random_device rnd;
  mt19937 mt(rnd());
  uniform_int_distribution<> rand_char(0, chars.length() - 1);

  while (tail != goal)
  {
    int r = rand_char(mt);
    tail += chars[r];
    if (tail.length() > goal.length()) {
      tail = tail.substr(1, goal.length());
    }
    count++;
  }

  cout << count << "文字目" << endl;
  cout << tail << endl;
}