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

トップページアルゴリズムとデータ構造編【その他のアルゴリズム】第2章

問題①

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


実際に2つのアルゴリズムでランダムシャッフルを行い、その結果が、可能性がある結果のパターンのどれに一致するかをカウントします。

ここでは、配列の要素数を 3 にします。可能性がある結果のパターンは6通りですから、偏りがなければ、各パターンの登場確率が 16.666% (100 / 6) ずつになるはずです。

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

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

typedef void (*shuffle_func)(int*, size_t);

enum {
    ARRAY_SIZE = 3,
};
static const int INIT_ARRAY_DATA[ARRAY_SIZE] = {0, 1, 2};
static const int ARRAY_PATTURN[][ARRAY_SIZE] = {
    {0, 1, 2},
    {0, 2, 1},
    {1, 0, 2},
    {1, 2, 0},
    {2, 0, 1},
    {2, 1, 0},
};

static void test_run(shuffle_func func);
static void random_shuffle(int* array, size_t size);
static void random_shuffle_ex(int* array, size_t size);
static size_t search_patturn(const int* array, size_t size);

int main(void)
{
    srand( (unsigned int)time(NULL) );

    test_run( random_shuffle );
    test_run( random_shuffle_ex );

    return 0;
}

/*
    指定したシャッフル関数でテスト実行開始
*/
void test_run(shuffle_func func)
{
    static const size_t RUN_COUNT = 1000000;  // 実行回数

    int array[ARRAY_SIZE];
    size_t patturn_count[SIZE_OF_ARRAY(ARRAY_PATTURN)] = {0};
    size_t patturn_index;

    for( size_t i = 0; i < RUN_COUNT; ++i){
        memcpy( array, INIT_ARRAY_DATA, sizeof(INIT_ARRAY_DATA) );
        func( array, SIZE_OF_ARRAY(array) );
        patturn_index = search_patturn( array, SIZE_OF_ARRAY(array) );
        patturn_count[patturn_index]++;
    }

    for( size_t i = 0; i < SIZE_OF_ARRAY(patturn_count); ++i){
        printf("%zu: %zu  (%.1f%%)\n",
            i,
            patturn_count[i],
            (double)patturn_count[i] * 100.0 / RUN_COUNT
        );
    }
    printf("\n\n");
}

/*
    配列の要素をランダムシャッフルする(良くない方法)
*/
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] );
    }
}

/*
    配列の要素をランダムシャッフルする(Fisher-Yates shuffle)
*/
void random_shuffle_ex(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] );
    }
}

/*
    並び順のパターンを探す
*/
size_t search_patturn(const int* array, size_t size)
{
    for( size_t i = 0; i < SIZE_OF_ARRAY(ARRAY_PATTURN); ++i ){
        if(memcmp(array, ARRAY_PATTURN[i], sizeof(int)*ARRAY_SIZE) == 0){
            return i;
        }
    }

    assert(!"該当するパターンが見つからない");
    return ~0;
}

実行すると、次のような結果を得られました。

0: 185204  (18.520%)
1: 172666  (17.267%)
2: 172187  (17.219%)
3: 148801  (14.880%)
4: 148686  (14.869%)
5: 172456  (17.246%)


0: 166292  (16.629%)
1: 167134  (16.713%)
2: 165984  (16.598%)
3: 167277  (16.728%)
4: 166795  (16.680%)
5: 166518  (16.652%)

それぞれ、最初の 6個が、良くない方法でのランダムシャッフルの結果で、後ろの 6個が Fisher-Yates shuffle での結果です。それぞれ、100万回のランダムシャッフルを行い、その結果のパターン(全部で6パターン)のどれになったかを出力しています。() の中は、全体の何パーセントの割合で、そのパターンが登場しているかを出力してあります。

理想的には 16.666% ぐらいずつに分かれてほしいですが、良くない方法では、14.219% ~ 18.520% という結果になりました。出やすいパターンと出にくいパターンのあいだに、4% 程度もの開きがあります。

一方、Fisher-Yates shuffle では、ほぼ均等に 16.666% に近い結果になっています。ほとんど偏りが起こっていないことが分かります。


参考リンク


更新履歴

’2015/12/27 SIZE_OF_ARRAYマクロの定義を修正。

’2015/2/21 サンプルプログラムで、ファイルスコープでよい関数に static を付加。

’2012/5/19 新規作成。



第2章のメインページへ

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

Programming Place Plus のトップページへ



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