このページでは、「重複なしで乱数を生成する方法」について解説していきます。乱数というよりも乱数列を生成すると言ったほうが、もしかしたらしっくりくるかもしれないです。
乱数の生成方法については下記ページで解説しており、乱数は rand
関数により生成(取得)することが可能です。
ただし、rand
関数を単に実行するだけだと生成する乱数が重複する可能性があります。
例えばトランプゲームなんかを作ろうと思うと、同じ乱数が生成されてしまうと同じカードを配ってしまうことになり、トランプゲームとして破綻してしまうようなこともあり得ます。
こんな時のために、重複なしで乱数を生成する方法を知っておくと便利です。
このページでは、その「重複なしで乱数を生成する方法」について解説していきます。
Contents
考え方:重複なしのデータ列をシャッフルする
この重複なしの乱数の生成は「重複なしのデータ列をシャッフルする」ことで実現することができます。もう少し具体的に言えば、重複なしのデータ列の各データの位置をランダムに入れ替えていくことで実現できます。
データ列とは C言語 の場合は配列と考えてしまって良いです。で、その配列には重複なしでデータを格納しておきます。そうすれば、シャッフル後も当然配列の各データが重複することはありません。
ただし、シャッフルすることでデータの並び順がランダムに変わります。したがって、この配列の先頭のデータから取得していけば、重複なしの乱数を生成していくことができることになります。
ここからは、「重複なしのデータ列をシャッフルする」ために必要な具体的な手順の解説や実装例の紹介を行なっていきます。
手順1:重複なしのデータ列を用意する
まず最初に「乱数として生成したい範囲」の値を格納した配列を用意します。値が重複さえしていなければ、どのような順番で配列に値が格納されていても問題ありません。
例えば、1
〜 100
の範囲の値から乱数を生成したい場合、下記のような単純なループにより、乱数として生成したい範囲の値を重複なしに格納した配列 array
を得ることができます。
int i;
int array[100];
for (i = 0; i < 100; i++) {
array[i] = i + 1;
}
また、例えば 1000
〜 1999
の範囲の偶数のみの値から乱数を生成したいのであれば、下記のようなループを実行すれば良いです。
int i;
int array[500];
for (i = 0; i < 500; i++) {
array[i] = 1000 + i * 2;
}
このような感じで、乱数として生成したい範囲に応じて配列の作り方を変更していただければと思います。
スポンサーリンク
手順2:データ列をシャッフルする(Fisher–Yates shuffle)
続いて先程作成した重複なしのデータ列(各データの値が重複していない配列)の中身をシャッフルしていきます。
シャッフルの仕方もいろいろ考えられますが、シャッフル後のデータの並びに偏りが出ないようなアルゴリズム(しかも処理速度的にも使用メモリ量的にも効率が良い!)として Fisher–Yates shuffle(フィッシャー – イェーツのシャッフル)がありますので、ここではこのアルゴリズムを利用してシャッフルすることにしたいと思います。
Fisher–Yates shuffle に関しては Wikipedia で解説されていますので、詳細を知りたい方は下記ページを読んでみてください。
https://ja.wikipedia.org/wiki/フィッシャー–イェーツのシャッフル
下記の shuffle
関数は、データの個数が size
の配列 array
を Fisher–Yates shuffle に則ってシャッフルする関数の実装例となります。この関数は上記 Wikipedia のページの特に 改良されたアルゴリズム で紹介されているものを実装した例となります。
#include <stdlib.h>
void shuffle(int array[], int size) {
int i, j;
int tmp;
/* シャッフル対象の末尾を設定 */
i = size - 1;
while (i > 0) {
/* シャッフル対象(0〜i)から位置をランダム決定 */
j = rand() % (i + 1);
/* ランダムに決めた位置と
シャッフル対象の末尾の位置のデータを交換 */
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
/* シャッフル対象の範囲を狭める */
i--;
}
}
下記の引数を指定して上記 shuffle
関数を実行すれば、重複なしのデータ列の各データの位置がシャッフルされ、ランダムに並んだ重複なしのデータ列を得ることができます(shuffle
関数を実行すれば第1引数で指定した配列のデータの並びが直接変更されることになります)。
- 第1引数:重複なしのデータ列を用意する で用意した配列
- 第2引数:第1引数に指定する配列のデータの個数
一応 shuffle
関数の処理の流れについて解説しておくと、一言でいえば、shuffle
関数はランダムに選択したデータを配列の末尾から順に並べていくことで配列全体をシャッフルする関数になります。
まず i
はシャッフルを行う対象となる範囲の末尾を示す変数です。
shuffle
関数では第1引数で指定された配列の全データに対してシャッフルを行うため、最初に i = size - 1
を設定しています。
以降では、このシャッフルを行う対象となる範囲を “シャッフル範囲” と略して呼ばせていただきます。シャッフル範囲の先頭は常に 0
となります。
続いて、シャッフル範囲のデータの中から1つデータをランダムに選択します。シャッフル範囲のデータは array[0]
〜 array[i]
ですので、rand() % (i + 1)
によりこのランダムな選択(添字の選択)を行います。
さらに、先程選んだデータをシャッフル範囲の末尾にあるデータ(すなわち array[i]
)と交換します。これにより、ランダムに選んだデータがシャッフル範囲の末尾に移動することになります。
ここで、交換後のシャッフル範囲の “末尾の位置のデータ” の位置を確定したものとし、そのデータをシャッフル範囲から追い出すためにシャッフル範囲を1つ狭めます。シャッフル範囲の末尾の位置は変数 i
で管理していますので、これは i
を 1
減らすことで実現することができます。
あとはこの繰り返しで、シャッフル範囲からランダムにデータを1つ選び、そのデータとシャッフル範囲の末尾のデータを交換し、さらにまたシャッフル範囲を狭めていきます。シャッフル範囲が狭まるということは、位置が確定したデータの個数が増えていくことにもなります。
繰り返していけばシャッフル範囲がどんどん狭まっていき、いずれはシャッフル範囲にデータが1つしか存在しなくなります。こうなるともう交換ができませんので、その時点でシャッフルは完了となります(図の配列の中身はてきとうです)。
この時、元々の配列の各データがランダムに選択した順番の逆順に並び変わっていますので、元々の配列をシャッフルできていることになります。
以上が shuffle
関数で行っている処理の解説となります。
もっと簡単に言えば、元々の配列からランダムな順番で取り出したデータを他の配列の後ろから並べていくのと同じようなことを行なっています(取り出したデータは元々の配列からは削除する)。
この並び替えを、1つの配列で効率よく実現しているのが上記の shuffle
関数となります。
手順3:シャッフル後のデータ列からデータを取得する
重複なしのデータ列を用意する で用意した配列に対して データ列をシャッフルする(Fisher–Yates shuffle) で紹介した方法でシャッフルを行えば、重複なしかつランダムに並び替えられたデータ列を取得することができます。
ですので、あとはこのデータ列の先頭からデータを取得していくだけで、重複なしの乱数を生成(取得)することができることになります(先頭でなくても末尾からでも良いです)。
例えば下記は、重複なしの乱数を生成(取得)しながら処理を行う一例となります(array
を shuffle
関数の第1引数に指定した int
型の配列として記述しています)。
for (i = 0; i < 10; i++) {
/* 重複なしの乱数を生成(取得) */
int random_number = array[i];
printf("%d\n",random_number);
}
上記は printf
で生成した乱数を表示するだけになりますが、ここを変更してやれば生成した乱数を使っていろんな処理を行うことができるようになります。
重複なしの乱数を生成するプログラム
ここまで紹介してきた一連の流れを実行するプログラムのソースコード例は下記のようになります。1
〜 100
の範囲の中から重複なしの乱数を 10
個生成する例となります。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
void shuffle(int array[], unsigned int size) {
unsigned int i, j;
int tmp;
/* シャッフル範囲の末尾を設定 */
i = size - 1;
while (i > 0) {
/* シャッフル範囲(0〜i)からランダムに1つデータを選択 */
j = rand() % (i + 1);
/* ランダムに決めたデータとシャッフル範囲の末尾のデータを交換 */
tmp = array[j];
array[j] = array[i];
array[i] = tmp;
/* シャッフル範囲を狭める */
i--;
}
}
int main(void) {
int i;
int array[100];
int random_number;
/* 種を初期化 */
srand((unsigned int)time(NULL));
/* 乱数の範囲は1〜100 */
for (i = 0; i < 100; i++) {
array[i] = i + 1;
}
/* arrayの中身をシャッフル */
shuffle(array, sizeof(array) / sizeof(array[0]));
for (i = 0; i < 10; i++) {
/* 重複なしの乱数を生成(取得)*/
random_number = array[i];
printf("%d\n",random_number);
}
return 0;
}
上記の main
関数から実行している srand
関数については下記ページで解説していますので、どのような関数かご存知ない方は是非読んでみてください。
スポンサーリンク
重複なしの乱数を生成する他の方法
その他にも、シャッフルは利用せずに、重複なしの乱数が取得できるまで rand
関数の実行を繰り返す方法もあります。
下記はその方法で重複なしの乱数を生成するプログラムのソースコードで、1
〜 1000000
の範囲から 10
個のみの重複なし乱数を生成する例になります。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_RANDOM_NUMBER 10
int main(void) {
int array[NUM_RANDOM_NUMBER];
unsigned int i;
int data;
unsigned int num_data;
int new_flag;
srand((unsigned int)(time(NULL)));
/* arrayに格納したデータ数を0にセット */
num_data = 0;
/* arrayがいっぱいになるまでループ */
while (num_data < NUM_RANDOM_NUMBER) {
/* 重複なしフラグをONにセット */
new_flag = 1;
/* 1〜1000000の中から乱数を取得 */
data = (rand() % 1000000) + 1;
/* arrayの全データとdataを比較 */
for (i = 0; i < num_data; i++) {
if (data == array[i]) {
/* 同じデータがあった場合は重複なしフラグをOFFにセット */
new_flag = 0;
break;
}
}
if (new_flag == 1) {
/* 重複なしフラグがONの場合 */
/* 重複なしなのでarrayに格納 */
array[num_data] = data;
/* 格納済みデータ数を増やす */
num_data++;
}
}
for (i = 0; i < NUM_RANDOM_NUMBER; i++) {
printf("%d\n", array[i]);
}
return 0;
}
配列 array
の中に存在しないデータが rand
関数から取得できた場合のみ、そのデータを配列 array
に格納するようにすることで重複なしの乱数列を生成できるようにしています(既に配列 array
の中に存在する場合は、そのデータは破棄して再度 rand
関数で新たなデータを取得する)。
重複なしのデータが rand
関数で取得できるまで何回も繰り返す必要があるので、シャッフルする方法に比べると遅いケースが多いです。速度が安定するのはシャッフルする方法の方です。
ただし、上記のように生成されうる乱数の範囲は大きいのにもかかわらず実際に必要な乱数の個数が極端に小さい場合は、この方法の方が効率が良い場合が多いと思います。
例えば 1
〜 1000000
の範囲から乱数を重複なしで生成する場合、シャッフルする方法だと 10
個のみの重複なし乱数の生成のためにも 1000000
個分のデータが格納可能な配列が必要になってしまって使用メモリ効率が悪いです。それに対して上記の方法であれば、生成したい乱数の個数である 10
個分のデータが格納可能な配列で済みます。
重複なしの乱数の生成を行う際には、基本的には最初に紹介したシャッフルの方法が無難だと思いますが、場合によってはこちらの方法も使えると思いますので、考え方は覚えておくと良いと思います!
まとめ
このページでは、C言語で重複なしの乱数を生成するための方法について解説しました!
具体的には、下記の手順により重複なしの乱数を生成することができます。
- 重複なしのデータ列を生成する(並び順はなんでも良い)
- 重複なしのデータ列の中身をシャッフルする
- シャッフル後のデータ列の先頭からデータを取得する
考え方としてはトランプのカードをシャッフルするのと似てるかなぁと思います。
また、重複しないデータが得られるまで rand
関数を繰り返すような方法もあり、この方法に関しては生成したい乱数の範囲に対して実際に生成する乱数の個数が極端に小さい場合に有効です。ただ、基本的にはシャッフルする手順の方が速度は安定するので無難だと思います。
トランプなどでは重複なしにランダムにカードを配るような処理が必要になりますので、今回紹介した方法はこういったゲームを作成するようなときに便利だと思います。
実際に下記のページでは、ポーカーで配るカードを決める際に今回紹介した方法での乱数生成を行なっています。興味のある方は是非下記ページも読んでみてください!
【C言語】ポーカーの作り方オススメの参考書(PR)
C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです!
まず学習を進める上で、参考書は2冊持っておくことをオススメします。この理由は下記の2つです。
- 参考書によって、解説の仕方は異なる
- 読み手によって、理解しやすい解説の仕方は異なる
ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね!」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか?
それと同じで、1冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。
なので、参考書は2冊持っておいた方が学習時に挫折しにくいというのが私の考えです。
特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか?」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。
もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう!もちろん私のサイトも参考にしていただけると嬉しいです!
入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。
https://daeudaeu.com/c_reference_book/