2009年3月28日

重複無しランダム抽出

学生が配列から重複なくランダムに値を抜き出すアルゴリズムを

乱数で生成した値を配列添字として配列から値を抽出、その値(または添字)を別配列に納め、重複が無いか配列をループ比較で確認し、重複があれば再度乱数で・・・


みたいに、ややこしく考えててねぇ。


簡単に考えた方が良いよって事で、擬似言語チックに例を。

rnd 整数型:関数random()で生成した乱数を納める
num 整数型:抽出したい数量
array 文字型配列:抽出対象配列 添字は0から
配列.length 配列要素数
random(整数値) 0から整数値-1の範囲で乱数生成
print()、for()は察して。
あと、num < array.length 前提って事で。
あと、num <= array.length 前提って事で。

で、実際のアルゴリズムは

for ( i = 0; i < num; i++ ) {
 rnd = random( array.length - i );
 print( array[ rnd ] );
 array[ rnd ] = array[ array.length - 1 - i ];
}

たったこんだけでおk!



って事で引き続き仕事するよぉ・・・。

4 件のコメント:

  1. うほ・・・わからん・・・

    返信削除
  2. チミが解らん訳ないやろー。

    ちなみに一箇所間違えてたんで修正したよー。

    つか、オイラが間違えてたせいで解らんかったんかも。
    もっかい考えてみて。

    返信削除
  3. 取り出した要素のところに最後尾の要素を持ってきて、iが増えることで探す範囲を一つずつ減らしてるんですかね?

    配列を使うプログラムを最近組んでないから考えるのに時間がかかったなぁ。これで違ったら恥ずかしい。

    num <= array.length じゃーないのかな?

    返信削除
  4. いえぁ、バッチリ。

    てか

    >> num <= array.length じゃーないのかな?

    指摘の通りやねw
    修正しとくー

    返信削除