ランダムシャッフル | Programming Place Plus　アルゴリズムとデータ構造編【その他のアルゴリズム】　第２章

トップページ – アルゴリズムとデータ構造編

この章の概要 🔗

この章の概要です。


ランダムシャッフル 🔗

この章では、配列の中にある要素を、ランダムな順番に並べ替えるという操作について考えてみます。この操作をランダムシャッフルと呼びます。

次のような配列を対象とします。

int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

良くない方法 🔗

ランダムシャッフルの方法はいくつか考えられると思いますが、よくある手段の１つは、乱数を使って２つの要素を選び出して、それらを交換する方法です。プログラムにすると、次のようになります。

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

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))
#define SWAP(type,a,b)          { type work = a; a = b; b = work; }

static void random_shuffle(int* array, size_t size);
static void print_array(const int* array, size_t size);

int main(void)
{
    int array[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    srand( (unsigned int)time(NULL) );

    random_shuffle( array, SIZE_OF_ARRAY(array) );
    print_array( array, SIZE_OF_ARRAY(array) );

    return 0;
}

/*
    配列の要素をランダムシャッフルする
*/
void random_shuffle(int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        size_t a = rand() % size;
        size_t b = rand() % size;
        SWAP( int, array[a], array[b] );
    }
}

/*
    配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
    for( size_t i = 0; i < size; ++i ){
        printf( "%d ", array[i] );
    }
    printf( "\n" );
}

実行結果：

2 5 4 3 8 7 1 0 9 6

実行結果を見ると分かるように、確かにシャッフルできています。特に問題ないように思えますが、実際にはあまり良い方法ではありません。

まず、forループをまわす回数に根拠がありません。配列の要素数分だけ回していますが、なぜ要素数を使えばいいといえるのでしょうか？　要素数10 の配列に対して、10回の交換を行うことが十分なのか不十分なのか。あるいは、実は過剰にまわし過ぎていて、無駄に処理速度を落としているかもしれません。また、要素数が 100 に増えたとき、交換回数はどう増えるべきなのかもよくわかりません。

そして、それに関係して、このような実装では、結果に偏りが出ます。偏りが出るということの意味については、のちほどあらためて取り上げることにして、まずは適切なランダムシャッフルのアルゴリズムを紹介します。


Fisher-Yates shuffle 🔗

ランダムシャッフルを行うには、Fisher-Yates shuffle というアルゴリズムを使うと良いです。

フィッシャー-イェーツ と読みます。

Fisher-Yates shuffle は、配列全体の中から１つの要素をランダムで選び出し、これを末尾の要素と交換することを繰り返すことで、偏りのないランダムシャッフルを実現します。

ここで、“末尾” の位置は、交換を行うごとに１つずつ手前へ移動していきます。つまり、後ろの方から確定されていくことになります。

Fisher-Yates shuffle を実装すると、次のようになります。

/*
    配列の要素をランダムシャッフルする
*/
void random_shuffle(int* array, size_t size)
{
    for( size_t i = size; i > 1; --i ){
        size_t a = i - 1;
        size_t b = rand() % i;
        SWAP( int, array[a], array[b] );
    }
}

よくない方法の実装では、交換する２つの要素の位置 a, b は両方とも乱数で生成されていました。それに対して、Fisher-Yates shuffle の場合は、a は配列の末尾から手前に向かって変化していき、b だけが乱数で生成されています。

forループは、配列の要素数-1回だけ繰り返されます。配列の要素数が 10 だとすると、繰り返し回数は 9回で、a の値は 9～1 まで変化します。b の値は、0 <= b <= a になるように乱数で生成されます。

a と b を両方とも乱数で決めると、１度も交換の対象にならない要素があり得ますが、Fisher-Yates shuffle の実装方法ならば、全要素を余すことなく、最低でも１回ずつ交換の対象になることが保証されます。これなら、少なくとも、繰り返し回数が不足していることはなさそうです。実際、この後の項で説明しますが、Fisher-Yates shuffle の繰り返し回数は必要十分な量になっています。

また、良くない方法と比べると、変数a には乱数を使っていないので、乱数を生成する回数が減っていることも分かります。これは、処理の高速化にもつながります。

なお、Fisher-Yates shuffle の計算量は O(n)です。

偏り 🔗

Fisher-Yates shuffle の場合、良くない方法と比べて結果の偏り具合も改善されています。

配列の要素数が 3 しかないとしましょう。

int array[] = {0, 1, 2};

この場合、ランダムシャッフル後の結果として考えられるパターンは、以下の 6通りです（順列の組み合わせなので、3! = 6 です）。

0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0

良くない方法の場合、交換する２つの要素の位置を乱数で決めているので、両方とも配列全体のどこかから選び出されます。つまり、0～2 のどこかが選択されますから、選ばれる場所には 3通りの可能性があります。よって、3 * 3 = 9通りの組み合わせがあります。

さらにこの交換処理を、配列の要素数分(=3) だけ繰り返しているので、93 = 729通りの結果が考えられます。もちろん、最終的なパターンはさきほどの 6通りしかあり得ないので、729通りのうちのほとんどが同じ結果の重複になります。

パターンが重複すること自体は問題ではありません。問題なのは、ランダムシャッフルの結果のパターンは 6通りなのに、729 % 6 をすると、3 という余りが出ているという点です。余り 3 が出るということは、6通りの結果のうちのどこか 3つのパターンが出やすくなっているということです。これが、結果が偏るという意味です。

これに対し、Fisher-Yates shuffle では、交換する２つの要素 a, b のうち、a は乱数に頼っておらず、b だけが乱数で決定されています。b が取り得る範囲は 0～a ですから、a == 2 である初回の組み合わせは、以下の３通りです。

a b
2 0
2 1
2 2

その次、a == 1 のときの組み合わせは、以下の２通りです。

a b
1 0
1 1

繰り返し回数は、配列の要素数-1回ですから、この時点で処理は完了しています。したがって、Fisher-Yates shuffle によって生み出される結果のパターンは、3 * 2 = 6通りとなります。すべての可能性を書き出すと次のようになります。

初回 b = 0, ２回目 b = 0 1 2 0
初回 b = 0, ２回目 b = 1 2 1 0
初回 b = 1, ２回目 b = 0 2 0 1
初回 b = 1, ２回目 b = 1 0 2 1
初回 b = 2, ２回目 b = 0 1 0 2
初回 b = 2, ２回目 b = 1 0 1 2

最初にみた、ランダムシャッフルの結果としてあり得る６通りのパターンがすべてあらわれていることがわかります。しかも、6 % 6 == 0 ですから、一部のパターンが重複しているということもありません。偏りなく、すべてのパターンが均等な確率であらわれるということです。

実際に偏り具合を確認するプログラムを練習問題で取り上げています。

まとめ 🔗

ランダムシャッフルの良くない方法と、Fisher-Yates shuffle による方法とを紹介しました。

良くない方法でも、一見して問題なく動いているように見えるため、あまり意識せず良くない方法を使ってしまうことがあると思いますが、実際には、結果は偏っている可能性が高いです。

また、不安感から、多めにループをまわすという逃げの策を打ってしまうかもしれません。結局のところ、たくさん回したからといって、偏りが解消するわけではなく、交換の対象になっていない要素が少なくなる（であろう）だけです。

Fisher-Yates shuffle の実装は非常に簡単ですから、ランダムシャッフルの実装が必要な場面では、つねにこの方法を使うのでも良いでしょう。

なお、Fisher-Yates shuffle の計算量は O(n)です。


練習問題 🔗

問題①　良くない方法と、Fisher-Yates shuffle とを使って、実際に結果の偏りがどの程度出るかを確認するプログラムを作成してください。


解答ページはこちら。


参考リンク 🔗


更新履歴 🔗


前の章へ　（第１章　交換のアルゴリズム）

次の章へ　（第３章　簡易的な暗号）

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る