C言語で重複しない乱数生成の仕方を教えてください！

Question

C言語で乱数を生成するときに、例えば１～１０の乱数を生成するとして、

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

int main()
{
int x;
for(int i = 0; i < 10; i++)
{
x = rand()%10+1;
printf("%d",x);
}
}

のようにすると実行結果が

2 8 5 1 1 0 5 9 9 3 5

のように値が重複していまします。

それを

1 3 9 7 4 6 2 5 8 10

のように値を重複させずに乱数を生成させる方法を教えてください！
よろしくお願いします！

Answer 1

ちゃんとFisher-Yatesでシャッフルするとこんな感じかと思います。

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

void shuffle(int array[], int size)
{
    int i = size;
    while (i > 1) {
        int j = rand() % i;
        i--;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

int main(int argc, char **argv)
{
    int values[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int size = sizeof(values) / sizeof(int);
    shuffle(values, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");
    return 0;
}

===={1,2,3}で10000000回試行したときの出現回数====
1 2 3: 1665490
1 3 2: 1667148
2 1 3: 1664647
2 3 1: 1666638
3 1 2: 1668634
3 2 1: 1667443

Fisher-Yatesってそんなに難解なアルゴリズムではないはずなのですが、
なぜか間違ってる例をよく見ますね。

Comments

[Chironian]

私の回答のリンク先の実装がFisher-Yatesと書きながら、そのようになってなかったのですね。なるほど。

私自身はFisher-Yates自体を把握してませんでした。乱数を簡単に使ってうまいことシャッフルできるアルゴリズムなのですね。すごい。

[raccy]

そそ、こっちこっち。ちゃんとn!の組み合わせになっているのが正しいのです。
結構間違うらしいですね。検索すると他にも間違って実装例がごろごろ転がっていました。

[YsMana]

考え方は単純で、
・乱数で要素を選択して
・選択した要素を退避して（退避先は配列の末尾、元々末尾にあった要素と入れ替え）
・要素が1つ減ったので乱数の範囲を1つ狭めて以降繰り返し
と、本当に要素を1つずつ取り出して並べてるだけなんですよね。

ただ、配列の後ろ側をシャッフル済み要素置き場にしていると思わずに
swapしているだけと考えてしまうと何をやっているか理解しにくいかもしれません。

Answer 2

こんにちは。

一旦配列に0～9まで入れておいて、その配列をシャッフルすると良いと思います。

以下、めめんと！「【C言語/C++】配列をシャッフルしてランダムに入れ替える」からの引用です。

#include<stdlib.h>
void shuffle(int ary[],int size)
{
    for(int i=0;i<size;i++)
    {
        int j = rand()%size;
        int t = ary[i];
        ary[i] = ary[j];
        ary[j] = t;
    }
}

Comments

[退会済みユーザー]

重複しない乱数を生成する事が出来ました！
ありがとうございます！

[raccy]

この実装は偏りがありませんか？
===={1,2,3}で1000000回試行したときのそれぞれの出現確率====
1 2 3 : 0.147903
1 3 2 : 0.184888
2 1 3 : 0.185185
2 3 1 : 0.185502
3 1 2 : 0.148641
3 2 1 : 0.147881

[Chironian]

raccyさん。

乱数生成関数を適切に選べば偏りは減らせます。どこまで偏りをなくすべきかは課題毎に異なりますので、必要に応じて選べば良いと思います。
今回はまあ、そこまでいらないのでは？　話題がそれてしまいますし。

[raccy]

いえ、rand()実装での偏りではなくて、shuffleの実装についてです。rand()のかわりにxorshiftで試して見ましたが、同じぐらい偏っていました。
https://ja.wikipedia.org/wiki/フィッシャー_-_イェーツのシャッフル
にある、「実装上の誤り」をまさにやっているように思えます。n!の組み合わせのはずが、n^nの組み合わせで選んでしまっているというところです。

[ozwk]

よく見るミスですね

[Chironian]

raccyさん。

あ、それも含めて乱数の偏りと表現しました。
RAND_MAXで割ってsizeをかければ元のrand()近くまで改善することは分かってますが、オーバーフロー対策が必要ですし、サンプルが見つからなかったし、今回はそこまでしなくて良いかな？と思ってます。

rand()%sizeでは偏りがあることを書いといた方が良かったかも知れませんね。
フォローありがとうございます。

[YsMana]

論点はそこではないですよ。
「rand()%size」を0以上size未満の整数を返すまったく偏りのない乱数源に置き換えたとしても、
実装しているアルゴリズム自体に問題があるのでシャッフル結果は偏ります。

[追記] あ、私の回答の方見て気付かれたようですね。
コード投稿しておいて良かった～。

Answer 3

配列に
1 3 9 7 4 6 2 5 8 10
と入れて順番に取り出せばいいです。

Answer 4

私が使っていた教本(「C入門と基本アルゴリズム」西東社、1992)には、こんなアルゴリズムが載っていました。

struct SHUFFLE
{
    int key;
    int order;
}randomizer;

int compfunc( const void* a, const void* b )
{
    struct SHUFFLE* p = (struct SHUFFLE*)a;
    struct SHUFFLE* q = (struct SHUFFLE*)q;

    if( p->order < q->order )   return -1;
    if( p->order > q->order )   return 1;
    return 0;
}

void shuffle(){
    int i;
    for( i = 0; i < sizeof( randomizer ) / sizeof( randomizer[0] ); i++ ){
        randomizer[i].key = i;
        randomizer[i].order = rand();
    }
    qsort( randomizer, sizeof( randomizer ) / sizeof( randomizer[0] ),
        sizeof( randomizer[0]), compfunc );
}

乱数の質次第ですが、結構均質ですよ。

Comments

[YsMana]

これはシュワルツ変換を利用したシャッフルですね。
rubyだと sort_by{rand} と凄く簡単に書けたりします。

割と良い結果を返すのですが、
rand()が異なる要素に対して同じ値を返したときの並び順はソートアルゴリズム次第で確定するので、完全に均質には混ざらないです。

あとは、乱数格納とソートが必要なので、Fisher-Yatesにくらべるとメモリ使用量と実行時間は不利ですね。

Answer 5

配列に予め 1 から 10 までの値を入れておき、その中身をランダムに並び替えてから表示したほうが良いでしょう。

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

void shuffle(int array[], int size)
{
    for (int i = 0; i < size; i++) {
        int j = rand() % size;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}

int main(int argc, char **argv)
{
    int values[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    int size = sizeof(values) / sizeof(int);
    shuffle(values, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", values[i]);
    }
}