「ホクホクのイモ」を考察する

元記事 https://qiita.com/mattn/items/d447a43ad12fada71663

自分がよく使ってる言語はコードゴルフにも難解プログラミングにも向いてないので、そっちで攻めるのではない記事にします。

仕様の考察

分解すると、まあこんな感じかと。

1. 「ホクイモ」の4字から、ランダムに、かつ重複せずに2文字取り出す。取り出す順番は考慮する。 (例："モホ")
2. 1. で取り出した文字を2回繰り返す。（例：「モホモホ」）
3. 1. と同じ処理をもう一度やりなおす。その際、さっき何を取り出したかは影響しない。（例："クモ"）
4. 1. と 3. の文字を「の」でつなぐ。（例：「モホモホのクモ」）

アルゴリズムの考察

「指定されたn字の中から、ランダムに、かつ重複せずにm文字取り出す。取り出す順番は考慮する。」のところが肝です。

• n字を順序付きコレクションに入れておいて、そのインデックスをm個ランダムに生成する。ただし、一度使ったインデックスはもう使えないようにする方法が必要（ビットパターンやブール値配列をフラグとして使うとか、集合に入れておくとかして、生成された数字が既出だったら再生成するなど）。
  • nに対してmが大きければ大きいほど、既出のインデックスが生成される確率が高くなるので、延々とループし続ける羽目になる。
• n字をコレクションに入れておいて、その要素をランダムに1つ選ぶ。そして、その要素（文字）をコレクションから取り除いて1字分小さくする。これをm回繰り返す。
  • コレクションのデータ構造によっては、コレクションから1字取り除くコストがそれなりにかかる。
• 最初にn字からm文字取り出す順列（permutation）をすべて並べあげて、その中からランダムに1つ選ぶ。
  • 順列をすべて並べ挙げた時の数は P(n, m) = n * (n-1) * ... * (n-m+1) = n! / (n-m)! になる。
  • バリエーションとして、0以上n未満の数で順列を作って、それを文字に対応付ける（順序付きコレクションのインデックスとして扱うなど）のもあり。
• n字を順序付きコレクションに入れておいて、最初にランダムシャッフルする。その後先頭からm文字取り出す。
  • 配列に入れておいて、配列のインデックス i を増やしながら、0以上i以下の数からランダムにjを選んで、要素iと要素jでシャッフルする。
    • 元の配列の要素を入れ替えて破壊的にシャッフルする方法と、新しい配列を初期化しながらシャッフルする方法がある。
  • ランダムな数列を長さnで作っておいて、その値をキーにしてコレクションをソートする。
  • リストをマージソートする際の比較をランダムにする。ただし、マージ元のリストの長さに比例して重みづけし、長い方のリストから選ばれやすくする。

このどれか（とはいえ最初のはやめた方がいい）の機構を提供する言語標準のライブラリーがあれば、短く書けて、なんかつよい感じがするのだけど、そういうのがない言語もあるわけですね。その場合はちょっとため息をつきつつ、自分で実装しましょう。

計算量については割愛しましたが、もし万が一コーディング面接で「ホクホクのイモ」が問われた時には、上のいくつか（全部とは言わないので、1つより多く）のアルゴリズムについて、計算量をきちんと見積もれれば、まあとりあえずその問題についてはOKなんじゃないでしょうか。