【C言語】重複なしで乱数を生成する方法

C言語で重複なしの乱数を生成する方法解説ページアイキャッチ

このページでは、「重複なしで乱数を生成する方法」について解説していきます。乱数というよりも乱数列を生成すると言ったほうが、もしかしたらしっくりくるかもしれないです。

乱数の生成方法については下記ページで解説しており、乱数は rand 関数により生成(取得)することが可能です。

C言語で乱数を扱う方法の解説ページアイキャッチC言語で乱数を扱う方法(rand関数とsrand関数)

ただし、rand 関数を単に実行するだけだと生成する乱数が重複する可能性があります。

例えばトランプゲームなんかを作ろうと思うと、同じ乱数が生成されてしまうと同じカードを配ってしまうことになり、トランプゲームとして破綻してしまうようなこともあり得ます。

乱数が重複することで発生する不具合の例を示す図

こんな時のために、重複なしで乱数を生成する方法を知っておくと便利です。

このページでは、その「重複なしで乱数を生成する方法」について解説していきます。

考え方:重複なしのデータ列をシャッフルする

この重複なしの乱数の生成は「重複なしのデータ列をシャッフルする」ことで実現することができます。もう少し具体的に言えば、重複なしのデータ列の各データの位置をランダムに入れ替えていくことで実現できます。

重複なしの乱数を生成する手順1

データ列とは C言語 の場合は配列と考えてしまって良いです。で、その配列には重複なしでデータを格納しておきます。そうすれば、シャッフル後も当然配列の各データが重複することはありません。

ただし、シャッフルすることでデータの並び順がランダムに変わります。したがって、この配列の先頭のデータから取得していけば、重複なしの乱数を生成していくことができることになります。

重複なしの乱数を生成する手順2

ここからは、「重複なしのデータ列をシャッフルする」ために必要な具体的な手順の解説や実装例の紹介を行なっていきます。

手順1:重複なしのデータ列を用意する

まず最初に「乱数として生成したい範囲」の値を格納した配列を用意します。値が重複さえしていなければ、どのような順番で配列に値が格納されていても問題ありません。

重複なしのデータ列を用意する様子

例えば、1100 の範囲の値から乱数を生成したい場合、下記のような単純なループにより、乱数として生成したい範囲の値を重複なしに格納した配列 array を得ることができます。

重複なしのデータ列の用意1
int i;
int array[100];
 
for (i = 0; i < 100; i++) {
    array[i] = i + 1;
}

また、例えば 10001999 の範囲の偶数のみの値から乱数を生成したいのであれば、下記のようなループを実行すれば良いです。

重複なしのデータ列の用意2
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引数で指定した配列のデータの並びが直接変更されることになります)。

一応 shuffle 関数の処理の流れについて解説しておくと、一言でいえば、shuffle 関数はランダムに選択したデータを配列の末尾から順に並べていくことで配列全体をシャッフルする関数になります。

まず i はシャッフルを行う対象となる範囲の末尾を示す変数です。

shuffle 関数では第1引数で指定された配列の全データに対してシャッフルを行うため、最初に i = size - 1 を設定しています。

shuffle関数における変数iの意味合いを示す図

以降では、このシャッフルを行う対象となる範囲を “シャッフル範囲” と略して呼ばせていただきます。シャッフル範囲の先頭は常に 0 となります。

続いて、シャッフル範囲のデータの中から1つデータをランダムに選択します。シャッフル範囲のデータは array[0]array[i] ですので、rand() % (i + 1) によりこのランダムな選択(添字の選択)を行います。

shuffle関数でシャッフル対象の中からデータをランダムに1つ選択する様子

さらに、先程選んだデータをシャッフル範囲の末尾にあるデータ(すなわち array[i])と交換します。これにより、ランダムに選んだデータがシャッフル範囲の末尾に移動することになります。

shuffle関数においてランダムに選択したデータとシャッフル範囲の末尾のデータを交換する様子

ここで、交換後のシャッフル範囲の “末尾の位置のデータ” の位置を確定したものとし、そのデータをシャッフル範囲から追い出すためにシャッフル範囲を1つ狭めます。シャッフル範囲の末尾の位置は変数 i で管理していますので、これは i1 減らすことで実現することができます。

shuffle関数において変数iをデクリメントすることでシャッフル範囲を狭める様子

あとはこの繰り返しで、シャッフル範囲からランダムにデータを1つ選び、そのデータとシャッフル範囲の末尾のデータを交換し、さらにまたシャッフル範囲を狭めていきます。シャッフル範囲が狭まるということは、位置が確定したデータの個数が増えていくことにもなります。

繰り返していけばシャッフル範囲がどんどん狭まっていき、いずれはシャッフル範囲にデータが1つしか存在しなくなります。こうなるともう交換ができませんので、その時点でシャッフルは完了となります(図の配列の中身はてきとうです)。

shuffle関数でデータの交換とシャッフル範囲の縮小を繰り返していく様子

この時、元々の配列の各データがランダムに選択した順番の逆順に並び変わっていますので、元々の配列をシャッフルできていることになります。

shuffle関数で変数iが0になったらシャッフルが完了していることを示す図

以上が shuffle 関数で行っている処理の解説となります。

もっと簡単に言えば、元々の配列からランダムな順番で取り出したデータを他の配列の後ろから並べていくのと同じようなことを行なっています(取り出したデータは元々の配列からは削除する)。

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 で生成した乱数を表示するだけになりますが、ここを変更してやれば生成した乱数を使っていろんな処理を行うことができるようになります。

重複なしの乱数を生成するプログラム

ここまで紹介してきた一連の流れを実行するプログラムのソースコード例は下記のようになります。1100 の範囲の中から重複なしの乱数を 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 関数については下記ページで解説していますので、どのような関数かご存知ない方は是非読んでみてください。

C言語で乱数を扱う方法の解説ページアイキャッチC言語で乱数を扱う方法(rand関数と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言語】ポーカーの作り方