C言語関係掲示板

過去ログ

No.60. 重複しないrand関数


rand関数を用いて 数字の羅列を作りたいです。そのとき、0から10の数字の
間で、10この数字を出力したときに、数字が重ならないようにしたいのですが、
どうしたら良いのか教えて下さい。
お願いします。


>rand関数を用いて 数字の羅列を作りたいです。そのとき、0から10の数字の
>間で、10この数字を出力したときに、数字が重ならないようにしたいのですが、
>どうしたら良いのか教えて下さい。

チェック用の配列を使うといいのではないでしょうか。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int rndck(int *tb);

int main(void)
{
        int r;
        int chktb[10] = {0};
        time_t t;

        /* 乱数系列の変更 */
        srand((unsigned) time(&t));

        /* 全て出現するまでループ */
        while ( rndck(chktb)==0 ) {
                r = rand() % 10;
                /* 未出現 */
                if (chktb[r] == 0) {
                        printf("%d ",r);
                        chktb[r] = 1;
                }
        }
        return(0);
}

/* 乱数発生チェック関数 */
int rndck(int *tb)
{
        int i;
        
        for (i=0; i<9; i++) {
                /* 未出現の整数があれば0返却 */
                if (*tb == 0) 
                        return(0);
                tb++;
        }
        /* 全て出現なら1返却 */
        return(1);
} 


間違っているところがありました。

> /* 乱数発生チェック関数 */
> int rndck(int *tb)
> {
> int i;
>
> for (i=0; i<9; i++) {

for (i=0; i<10; i++) {

でした。失礼しました。


「0から10の数字の間で…」ってことは候補は11個ですよね。
私はこうです。
---
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef enum { false, true } bool;

int main(void)
{
        bool check[11] = {false};
        int n, i;

        srand((unsigned)time(NULL));
        for ( i = 0; i < 10; i++ ) {
                do {
                        n = rand() % 11;
                } while ( check[n] );
                check[n] = true;
                printf("%d ", n);
        }

        return 0;
}


chuさんのプログラム、すっきりしていていいですよね。

> typedef enum { false, true } bool;

enum使った点も親切ですね。
こういう、単純な問題も、いろいろな解き方が考えられて面白いですよね。


10 個とかならその方法でもいいと思いますが、1000 個とかになると、
最後の方で、チェックされてないものを rand() が取ってくる可能性が
非常に低くなります。

 チェック用の配列を作り、もしチェックされていたら、要素の左右に
チェックされていない数字を探しに行きます。このようにすれば、random
な配列が割と良いコストで得られます。

 以下のプログラムは、同時にチェック用にもなっています。実行して
no errors!! と表示されれば、それは重複無く atrandom という配列に
0 から 999 までの数字が random に入っています。

 確認は BCC5.5.1 です。

 ホントはボク C++ 専門なんですが、C のソースを以下に示します。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int SearchForwardRandomValue(int index, int n, int* check);
int SearchBackwardRandomValue(int index, int* check);
int GetRandomValue(int n, int* check);
void GetRandomValueArray(int *atrandom, int n);

int main(void)
{
    time_t t;
    srand(unsigned(time(&t)));
    
    int atrandom[1000];
    int check[1000] = {0};
    int i;
    GetRandomValueArray(atrandom, 1000);

    for (i = 0; i < 1000; ++i){
        if (check[atrandom[i]] == 1) {
            printf("error!!\n");
            return 1;
        }
        check[atrandom[i]] = 1;
    }
    
    printf("no errors!!\n");
    return 0;
}

int SearchForwardRandomValue(int index, int n, int* check)
{
    int i;
    for (i = index; i < n; ++i) {
        if (!check[i]){
            return i;
        }
    }
    /* 見つからなかった */
    return -1;
}

int SearchBackwardRandomValue(int index, int* check)
{
    int i;
    for (i = index; i >= 0; --i) {
        if (!check[i]){
            return i;
        }
    }
    /* 見つからなかった */
    return -1;
}

int GetRandomValue(int n, int* check)
{
    int result, index;
    index = rand() % n;
    
    if (rand() % 2) {
        result = SearchForwardRandomValue(index, n, check);
        if (result == -1) {
            result = SearchBackwardRandomValue(index, check);
        }
    } else {
        result = SearchBackwardRandomValue(index, check);
        if (result == -1) {
            result = SearchForwardRandomValue(index, n, check);
        }
    }
    if (result != -1) {
        check[result] = 1;
    }
    return result;
}

void GetRandomValueArray(int *atrandom, int n)
{
    void *check = calloc(1000, sizeof(int)); /* 動的に確保 */

    for (int i = 0; i < n; ++i) {
        atrandom[i] = GetRandomValue(n, (int *)check);
    }
    
    free(check); /* 解放 */
}


こんにちは、ともじです。書き込みありがとうございます。

> 10 個とかならその方法でもいいと思いますが、1000 個とかになると、
>最後の方で、チェックされてないものを rand() が取ってくる可能性が
>非常に低くなります。
>
> チェック用の配列を作り、もしチェックされていたら、要素の左右に
>チェックされていない数字を探しに行きます。このようにすれば、random
>な配列が割と良いコストで得られます。

なるほど、二分探索を思わせるロジックですね。
mallocではなく、callocを使っている点はさすがです。(callocはメモリを
確保するときに0クリアします。)ということは、mainのint check[1000] = {0};
は不要ですかね。

ところで、私のと、chuさんのと、友葉さんのやり方で、乱数の精度をチェック
してみました。それぞれ、1,000,000回ずつループさせ、1〜9の乱数を発生
させ、初回〜10回目までに発生する数値をすべて加えてみました。

ともじ
addnum[0] = 4495757
addnum[1] = 4502937
addnum[2] = 4495660
addnum[3] = 4497236
addnum[4] = 4495060
addnum[5] = 4498957
addnum[6] = 4501235
addnum[7] = 4505579
addnum[8] = 4506767
addnum[9] = 4500812 差:4506767-4495060 = 11707

chuさん
addnum[0] = 4492518
addnum[1] = 4500606
addnum[2] = 4501931
addnum[3] = 4504542
addnum[4] = 4497619
addnum[5] = 4499982
addnum[6] = 4500068
addnum[7] = 4499841
addnum[8] = 4504393
addnum[9] = 4498500 差:4504542-4492518 = 12024

友葉さん
addnum[0] = 4499250
addnum[1] = 4500140
addnum[2] = 4501051
addnum[3] = 4498573
addnum[4] = 4500451
addnum[5] = 4497979
addnum[6] = 4502673
addnum[7] = 4497722
addnum[8] = 4501987
addnum[9] = 4500174 差:4502673-4497722 = 4951

ということで、友葉さんのやり方が一番差が少なかったのですよ。
何故こうなるのか、文系の私はわからないのですが、やり方で効率も精度も
結構違うものですよね。


>ということで、友葉さんのやり方が一番差が少なかったのですよ。
>何故こうなるのか、文系の私はわからないのですが、やり方で効率も精度も
>結構違うものですよね。
>

単にスピード重視をするなら、木構造やハッシュ表にしたら
高速になるような気がしますが如何なものでしょうか?

はずしてたらごめんなさい。


>単にスピード重視をするなら、木構造やハッシュ表にしたら
>高速になるような気がしますが如何なものでしょうか?

私が、「二分探索を思わせる」なんて書いたからいけないんですが、
この処理は、探索やソートとはちょっと違うので、木構造やハッシュは
使えないと思いますよ。

#友葉さんのやり方、単に二分割して未使用の数値を探しているだけで、
二分探索とは全然違います。「二分探索を思わせる」なんて書いてすみません。


ども。

チェック用の配列をつかわない、こんなのはどうでしょう?
ちゃんと検証していないので、どこかに+1がたりない等の
ミスがあるかもしれません。。

(1) a[1+N]を用意し、a[0]=0, a[1]=1, ..., a[N]=N というように初期化
(2) i=1+Nとし、i>0の間、(3)をくりかえす
(3) a[]のrand()%i番目とi番目を入れ替えて、i=i-1する
(4) できあがり(結果の数列はa[]に格納されています)

コストはN回ループx2です。あ、N+1回ループかな。

では。


>(1) a[1+N]を用意し、a[0]=0, a[1]=1, ..., a[N]=N というように初期化
>(2) i=1+Nとし、i>0の間、(3)をくりかえす
>(3) a[]のrand()%i番目とi番目を入れ替えて、i=i-1する
>(4) できあがり(結果の数列はa[]に格納されています)

 ボクもこれ考えてたんですが、やっぱどう考えてもこの方が楽。
コストも O(N) ですし。
 今まで議論していた方は、O(N^2)になりますしね・・・。←割とアホ

 難しい方向に持っていってしまった・・・
 これだから理系は・・・うぐぅ・・・


を組んでみたんですがkikkさんとアルゴリズムいっしょですね。
変なとこありましたらつっこみお願いします。

--- main.c -----------------------------
#include <stdio.h>
#include <time.h>
#include "crand.h"
int main(void)
{
        int i;
        scrand((unsigned)time(NULL), 0, 10);
        for ( i = 0; i < 10; i++ )
                printf("%d ", crand());
        fcrand();
        return 0;
}
--- lrand.h ----------------------------
void scrand(unsigned seed, int min, int max);
int  crand(void);
void fcrand(void);
--- lrand.c ----------------------------
#include "crand.h"
#include <stdlib.h>

static int   *table;
static size_t size;
static size_t pos;

static void swap(int *a, int *b);
static void shuffle(void);

void scrand(unsigned seed, int min, int max)
{
        size_t i;
        srand(seed);
        if ( max < min )
                swap(&max, &min);
        size = max - min + 1;
        table = (int *)malloc(sizeof(int) * size);
        for ( i = 0; i < size; i++ )
                table[i] = min + i;
        shuffle();
        pos = 0;
}

int crand(void)
{
        if ( pos > size - 1 ) {
                shuffle();
                pos = 0;
        }
        return table[pos++];
}

void fcrand(void)
{
        free(table);
}

void swap(int *a, int *b)
{
        int t = *a;
        *a = *b;
        *b = t;
}

void shuffle(void)
{
        size_t i, j;
        for ( i = 0; i < size; i++ ) {
                j = rand() % size;
                swap(&table[i], &table[j]);
        }
}


> 変なとこありましたらつっこみお願いします。

この例でも、0〜10までの数値から乱数10個を重複しないで選ぶ処理を
1,000,000回処理して合計値を調べてみました。

addnum[0] = 4567913
addnum[1] = 4726442
addnum[2] = 4865918
addnum[3] = 4982488
addnum[4] = 5076323
addnum[5] = 5138965
addnum[6] = 5182826
addnum[7] = 5190549
addnum[8] = 5162358
addnum[9] = 5109284 差:5190549-4567913 = 622636

この方法だと、shuffle()関数で可変のsizeで j = rand() % size; として
いるので、精度が悪くなるんでしょうね。

#自分では考えられないのに、つっこんですみません。(^_^;)


ども、友葉です。
 0 から n - 1 までの乱数を作成する方法として、rand % nはあまり
優れた方法ではないようです。乱数っていったって、疑似乱数
ですから、下位ビットには問題が多いです。

 ということで、BASIC な人たちは、次のように書くことがあります。
((double)rand()/RAND_MAX) * n

 これだと、若干改善されるみたいですけどね。

 あと、乱数の精度を比較するのには、range (MAX - MIN) をとるのではなくて、分散を考えた方が良いかと思います。

 あと、仮に rand() が完全に乱数を返してくれるという仮定のものと
では、chu さんのアルゴリズムは数学的に、完全な確からしさがありま
すし、コストも O(N) だし、これがベストだと思います。

 ボクのは昔不可変な集合から一つランダムにとってくる処理をしたくて
思いついた方法ですから、この処理にはあまり向かないと思います。
( チェック用の配列を用意する、というのでその方向で考えすぎた?)


> あと、仮に rand() が完全に乱数を返してくれるという仮定のものと
>では、chu さんのアルゴリズムは数学的に、完全な確からしさがありま
>すし、コストも O(N) だし、これがベストだと思います。

 失礼。chu さんではなくて、kikk さんです・・・。うぐぅ


ともじです。

> 0 から n - 1 までの乱数を作成する方法として、rand % nはあまり
>優れた方法ではないようです。乱数っていったって、疑似乱数
>ですから、下位ビットには問題が多いです。
>
> ということで、BASIC な人たちは、次のように書くことがあります。
>
> ((double)rand()/RAND_MAX) * n
> これだと、若干改善されるみたいですけどね。

ここの「13.16」に書いてありますね。
http://www.catnet.ne.jp/kouno/c_faq/c13.html


>> 0 から n - 1 までの乱数を作成する方法として、rand % nはあまり
>>優れた方法ではないようです。乱数っていったって、疑似乱数
>>ですから、下位ビットには問題が多いです。
>>

疑似乱数生成アルゴリズムというので、こんなサイトがありました。
http://www.math.keio.ac.jp/matsumoto/mt.html


> 0 から n - 1 までの乱数を作成する方法として、rand % nはあまり
>優れた方法ではないようです。乱数っていったって、疑似乱数
>ですから、下位ビットには問題が多いです。

なるほど、rand()って信頼性低いんですね。
勉強になりました、ありがとうございます。

でも、今のほとんどのrand()は信頼性が低いってわかってるのに
どうして違うアルゴリズムを採用しないんでしょう?
rand()実装者の手抜き?それとも他に理由でもあるんでしょうか?
やっぱり rand() % n って書きたいとこです。


今アルゴリズムの本眺めてたんですが、それのシャッフルコードが
for ( i = n - 1; i > 0; i-- )
となっていました。
kikkさんも
> 2) i=1+Nとし、i>0の間、(3)をくりかえす
と書いてらっしゃるんですが、(i=0→N-1)ではなにか問題が出てくるのでしょうか?


ども。

>今アルゴリズムの本眺めてたんですが、それのシャッフルコードが
> for ( i = n - 1; i > 0; i-- )
>となっていました。
>kikkさんも
>> 2) i=1+Nとし、i>0の間、(3)をくりかえす
>と書いてらっしゃるんですが、(i=0→N-1)ではなにか問題が出てくるのでしょうか?

べつにどっちでもいいとおもいます。たぶん。

ちなみに。
大きいほうからにしろ、小さいほうからにしろ、ループを1回実行すると
i要素の配列から1つランダムに取り出すという問題が、i-1要素から1つ
取り出すという問題になります。
大きいほうからにしたのは、数字と変数の対応が上記の通りになるので
そのほうが美しいと思ったからです。。

その本の著者の意図はわかりませんが。。。

では。


>大きいほうからにしたのは、数字と変数の対応が上記の通りになるので
>そのほうが美しいと思ったからです。。

あ、なるほど。
0との比較にしたほうが優秀なコードが生成されるのかなとかいろいろ考えてしまってました。
どうもありがとうございました。

戻る


「初心者のためのポイント学習C言語」 Last modified:2001.10.7
Copyright(c) 2000-2002 TOMOJI All Rights Reserved