選択問題の答えの候補を自動で作成するプログラム

質問

このジャンルでお願いします。

選択問題の回答候補を自動作成したいのですが、
例えば、4択問題で「あいうえ」が答えだとします。
１、「あいうえ」
２、「あいうお」
３、「おあいうえ」
４、「んかきく」

という文字の順番が関係ない（つまり4文字の「えういあ」はすでに「あいうえ」があるので候補にすることはできません）4択を
自動で作成したいのですが、どのようなプログラムにすれば良いのでしょうか？
自分で考えていて結構複雑だと思えたので、お聞きしたいのですが、
例えばこれ「あいうえ」を１、以外にも候補にできた（まあ問題として成立しませんが・・^^;）ら
単にランダムで選んでいけば良いと思いますが、その（並び順は関係ない）文字と文字数が一緒の場合は
もう候補にすることができないのです・・・上の例だと２、「あいうお」が候補になったので３、以降は
「あいうお」も候補にできません。そんなことを気にせず単にランダムで選んでいって、もし「あいうえ」が
出たらもう一度ランダムで別の候補が出るまでループする方法もあるとは思いますが、それだと効率が悪いというか
選択肢が（非現実的ではありますが）とても大きくなった場合に半ば無限ループ状態になりかねないと思うのでそれは違うと思いました。
どのようにすれば良いのかアドバイスを頂けないでしょうか？

回答No.4

axsies

例えば100個の選択肢候補の中から99個の選択肢を選びたいとします。
質問者さんの方法だと、99個目に近づくにつれ選ばれてない候補が少なくなって、再抽選の確率が高いので、こういう場合にも対応できる方法はないか？って話ですよね？

>「選択肢として選ばない組み合わせ」を抽選するアルゴリズムに切り替えるという手があります。

というのは、100個の中から99個の選択肢を選ぶのではなく、
100個の中から「選択肢として選ばないもの」を1個だけ選びだし、
残り99個を選択肢とすれば、再抽選の確率は低くなるということです。
（100個のうちから99個の場合は再抽選すら必要ありませんが）
選び出さなければならない選択肢の数が、候補の半分以下なら元の方法を使い、半分以上ならこの方法を使うようにアルゴリズムを切り替えれば、最悪の場合は候補の中から半分を選択肢として選ぶ時で、約1/2の確率で済みます。

ところで、このランダムループ方式(と呼ぶことにします)が無限ループになるかを心配されてますが、
このアルゴリズムが妥当かどうかは、まず再抽選の確率を考える必要があります。
確率pのものがn回連続で選ばれない確率は(1-p)^nです。
pは確率ですから、当然0<=p<=1ですので、p=0のとき以外は、n→∞のとき、(1-p)^nは0に収束します。
これは実行時間をどこまで許容するか？という問題を無視すれば、pの大きさにかかわらず、実質的に「必ず停止する」アルゴリズムです。
しかも(1-p)^nは指数関数ですから、pがどんなに小さくても(つまり、どんなに選ばれる可能性が低くても)試行を繰り返すほど選ばれない確率は爆発的に低くなっていきます。
実際問題そんな数百個の選択肢を選ぶ必要があるわけではないでしょうから、選択肢候補の数が多いほど、そもそも再抽選が行われる事自体が天文学的確率になっていくのです。

逆関数を計算すれば何％の確率で停止するのは何回くらいか、というのも導き出せます。
90%の確率で停止するのは
p=1/2なら、3回
p=1/1000なら、2301回
p=1/10000なら、23,024回程度です。
結果的に、作ろうとしてるプログラムの要件にとって、どのくらいのループ回数までなら許容できるのか？
という所が問題になってきます。
選択肢が膨大な数になると、最初の方法だけでは、ちょっと多すぎるかもしれません。
選択肢を表示するたびに選び出すのではなく、1日おきに何パターンか生成しておき、
表示するときはそのパターンの中から１つ選び出すようにすれば、最初の方法でも十分かもしれません。
実行環境のスペックとか、何PV/日くらい見積もっているのかとか、そういう要素を検討しなければ答えは出ません。

No3.の方の方法は、再抽選が必要ないよい方法だと思います。
実際当たるまで繰り返していると、実行時間が不安定になりますが、これはWebプログラミングでは問題かもしれません。
問題は、全候補をメモリ上にロードしなければならない点です。
候補がウン万、ウン十万あるのに選ぶのは4つだけ、とかの場合は非効率とも言えます。でも工夫次第です。
ランダムループ方式も、選択肢が膨大になってくると、既に選んだかどうかを比較する回数の方がネックになってきます。
まぁ万能なアルゴリズムというのは存在しないので、最後は割り切りです。

お礼

ご回答ありがとうございます。
＞99個目に近づくにつれ選ばれてない候補が少なくなって、再抽選の確率が高いので、こういう場合にも対応できる方法はないか？って話ですよね？
はい、その通りです。

＞候補の半分以下なら元の方法を使い、半分以上ならこの方法を使うようにアルゴリズムを切り替えれば、
なるほど、たしかにそのような方法も使えそうですね。
参考になりました。

今までランダムループ方式は自分としてはプログラム的に禁止（なし）だと思い込んでいたのですが、
そうではないわけですか・・
たしかに、それを使用するアプリケーション環境次第なんでしょうけど、
プログラムを利用するのは人間なわけですから、割り切ればいいわけですよね。

データベスのテーブルの構成をプログラム（PHP）的に再現して
そこからNo.3でyambejpさんも仰っていたように、ウエイトを加味して並べ替えして
先頭から３つ選べばできそうな気もするのですが、
そこでPHPで置き換えると次のような配列として現せると思います。

$tango_tbl = array(
array('文字' => 'あ'),
array('文字' => 'い'),
array('文字' => 'う'),
array('文字' => 'え'),
array('文字' => 'お'),
);

$kanren_tbl = array(
array('答え' => 'あいうえ', '関連候補' => 'あいう', '関連指数' => 10),
array('答え' => 'あいうえ', '関連候補' => 'おあいう', '関連指数' => 5),
);

これを「あいうえ」は答えとして、残り３つを候補として「関連指数」を基準にしてランダムに選び、
並べ替えたいのですが、それはPHPでは具体的にどのように記述すれば良いのでしょうか？
もしできそうであればアドバイス頂けないでしょうか？

回答No.3

yambejp

候補を配列にいれて、シャッフルし、前方から４つデータを抜けばよいでしょう

お礼

すいません、このジャンルで伺うことではないかもしませんが、
一応関連性はあると思いますし、もう既に質問を立ててしまったので伺いたいのですが、
データベースを利用すればこのようなことを実現できるのかな？と思ったのですが、
それは次のように、

「単語テーブル」
単語カラム
あさがお
ひるがお
ゆうがた
なつがお
ひまわり
ヒヤシンス

「関連候補テーブル」
答えカラム　　関連候補カラム　関連指数カラム（1～10まで）
あさがお　　　ひるがお　　　　　10
あさがお　　　よるがお　　　　　5
あさがお　　　ゆうがたがお　　 3
あさがお　　　なつがお　　　　　1

を用意して、
答えが「あさがお」の場合の4択候補の選び方として、
関連指数カラムを利用してウエイトを加味してランダムに抽出したいと思っているのですが、
例えば、「関連候補テーブル」の「あさがお」には「ひまわり」と「ヒヤシンス」を設定（挿入）していませんので、
これらの候補は「ひるがお」や「なつがお」よりも選ばれ難く（関連指数カラムが0）なるようにしたいのです。
問題の例も、データベースで条件付で検索してやればできそうな気がするのですが、
自分にははっきりどう記述すれば良いのかが分かりません・・・
つまり、「あいうえ」が答えなら4文字の場合だけ選出するときは注意すればよく、それをSQLで記述すると

$rows（4行（「お行あ行い行え行」など）） = select * from `ひらがな` WHERE `id` = (select id from `ひらがな` where `id` = （「あ」でもない「い」でもない「う」でもない「え」でもない　4文字の候補のid）) order by rand()(←ウエイトを加味した記述が分からないのでとりあえずランダムに) limit 4(←選択数)

こんな風なイメージになるのかと思いますが、もちろんこれではプログラムは動かないのですが、
もしご存知でしたらこのような抽出方法は可能でしょうか？

補足

すいません、、訂正で

（「あ」でもない「い」でもない「う」でもない「え」でもない　4文字の候補のid）
ではなくて
（4文字なら「あ」「い」「う」「え」の行の組み合わせは駄目という　4文字（行）のid）

非常に分かり難いかもしれませんが、なんとか伝わって欲しいと願います。。。

回答No.2

axsies

仮に選択肢の数が膨大な場合を考えるとすると、
「選択肢として選ばない組み合わせ」を抽選するアルゴリズムに切り替えるという手があります。

お礼

ご回答ありがとうございます。
それは具体的にどのような手法なのでしょうか？

回答No.1

osamuy

「あ」～「ん」からなる4文字の組み合わせ数は約15万(重複を許さない場合)ですから、

＞ランダムで別の候補が出るまでループする方法

で十分かと。現実的に考えて。

お礼

ご回答ありがとうございます。
自分もその方こそが現実的だとは思ってきてはいるのですが、
ただそれだとプログラム的にループの繰り返す長さをランダムに依存させて良いのかな？というのがありまして、無限に続く可能性は0ではないですよね？（まあ天文学的数字以上に低いでしょけど）
なのでこのような質問をしたというのがあります。