乱数について

質問

今、あるデータの順番をばらばらにするプログラムを作ろうとしています。

　たとえば、a,b,c,dとあったら、d,b,c,aとするように、この時考えられるプログラムは、データの数だけ配列を用意して、乱数で、どのデータを出力させるかを決定し、出力し終わったら、その配列のところに印を立てて、次にくるデータに対して、2重にならないように順次、出力していく方法が考えられるのですが。。。

　膨大なデータをこのように、すると、二重になる確立が出力するたびに、高くなっていって、なかなか終わらなくなってしまいます。

　そこで、残ったデータから、ランダムに選び出すアルゴリズムまたは、関数はないでしょうか？よろしくお願いします。

回答No.1

nakashi · ベストアンサー

データの数だけ配列を用意して、乱数で適当な回数、場所を入れ替えて
(シャフルして)から

先頭から順番に取れば?

お礼

なるほど！以外に単純でしたね。
ありがとうがございました。

回答No.4

ymmasayan

No.1の方の方式（仮にＡとします）とNo.3の方の方式（仮にＢとします）がよく使われます。
バッチ的な処理ではＡが適しています。（前処理に時間がかかってもいいが、処理をはじめたら高速）
一方、リアルタイム処理ではＢが適しています。（前処理がいらず、毎回一定時間で処理可能）
全部終わったら又、対象を広げて続けると言う場合、Ａでは、又、シャッフルが必要ですが、Ｂでは対象範囲を広げるだけでいいので一瞬ですみます。

特別にまずいという理由がなければ、Ｂ方式をお勧めします。私はいつもＢ方式を使っています。

お礼

なるほど。勉強になります。

2種類の方法がでているので、ポイントはあげられませんが、ありがとうございました。m (_ _) m

回答No.3

noname#30727

乱数の範囲を狭めていき、選択されたものを次に選択されない位置に移動させるようにします。

#define N 10
int a[N];
int i, r, t;

for (i = 0; i < (N - 1); i++)
{
// i の位置から最後までの中で１つ選択
r = i + rand() % (N - i);

// 選択したものを i の位置と交換する
t = a[i];
a[i] = a[r];
a[r] = t;
}

for (i = 0; i < N; i++)
{
出力(a[i]);
}

お礼

ほ～
非常に勉強になりました。そういう方法もあるんですね。

ありがとうございました。

回答No.2

ranx

実データとは別に、それに対するインデックスまたはポインタの配列を作ります。
例えば
　1 - a
　2 - b
　3 - c
　4 - d
という感じです。
乱数で、インデックスを選択し、対応するデータを出力します。
例えば上の例で3が選択されたらcです。
選択されたインデックスを取り除きます。すると
　1 - a
　2 - b
　4 - d
　　　cはインデックスなし
となります。
残ったインデックスから乱数で一つを選択し、インデックスが
無くなるまでこれを続けます。

お礼

>残ったインデックスから乱数で一つを選択し

いや、その残ったインデックスから、どのように選択するのか知りたかったものですから。。乱数で選択すると、重なる部分が出てくるわけじゃないですか。そうすると、選択するたびに、重なる部分が多くなるので、処理速度が遅くなるので、残ったインデックスからどのように、乱数で選択するのかを聞きたかったのですが。。。

ご意見　ありがとうございました。