マルコフ連鎖、しかのこしかのここしたんたん

「し」からは「か」と「た」にそれぞれ1/2の確率で移動。
「か」から「の」へは100%で移動。
「の」から「こ」へは100%で移動。
「こ」から「の」へは1/2の確率で移動し、「こ」に戻るのが1/4、「し」へは1/4の確率で移動。
「た」から「ん」へは100%で移動。
「ん」から「た」と「＿」にそれぞれ1/2の確率で移動。
「＿」から「＿」と「し」にそれぞれ1/2の確率で移動。

14文字のパターンをすべて列挙

koshitan.pde

// マルコフ連鎖：状態 = {し, か, の, こ, た, ん, _}
// スタート：し
// 長さ：14文字（先頭の「し」を含む）
// 出力：全列挙を patterns.txt に保存、件数をコンソール表示

import java.util.*;

// 設定
final int TARGET_LEN = 14;        // 列挙する総文字数（先頭の「し」を含む）
final String START = "し";         // 開始文字

// 遷移表（確率は説明上のもので、列挙では「遷移可能かどうか」だけ使う）
HashMap<String, String[]> nexts = new HashMap<String, String[]>();

ArrayList<String> results = new ArrayList<String>();

void setup() {
  size(800, 600); // 何でもOK（描画は使わない）
  surface.setVisible(false); // ウィンドウ非表示でもOK（必要なら残して）

  // 遷移定義
  // 「し」→「か」「た」 (各1/2)
  nexts.put("し", new String[]{"か", "た"});
  // 「か」→「の」 (100%)
  nexts.put("か", new String[]{"の"});
  // 「の」→「こ」 (100%)
  nexts.put("の", new String[]{"こ"});
  // 「こ」→「の」(1/2)、「こ」(1/4)、「し」(1/4)
  nexts.put("こ", new String[]{"の", "こ", "し"});
  // 「た」→「ん」 (100%)
  nexts.put("た", new String[]{"ん"});
  // 「ん」→「た」「＿」 (各1/2)
  nexts.put("ん", new String[]{"た", "＿"});
  // 「＿」→「＿」「し」 (各1/2)
  nexts.put("＿", new String[]{"＿", "し"});

  // 列挙実行
  StringBuilder sb = new StringBuilder();
  sb.append(START);
  dfs(START, 1, sb); // 現在長 = 1（先頭「し」を入れた状態）

  // 保存
  saveStrings("patterns.txt", results.toArray(new String[0]));
  println("総パターン数 = " + results.size());
  println("全パターンは patterns.txt に保存しました。");

  exit(); // 終了
}

// 深さ優先で全列挙（非確率的：遷移可能なすべての枝を探索）
void dfs(String cur, int len, StringBuilder sb) {
  if (len == TARGET_LEN) {
    results.add(sb.toString());
    return;
  }
  String[] ns = nexts.get(cur);
  if (ns == null) return; // 念のため（未定義状態は打ち切り）

  for (String nx : ns) {
    // 追加
    sb.append(nx);
    dfs(nx, len + 1, sb);
    // 戻す
    sb.setLength(sb.length() - nx.length());
  }
}