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

先頭へ戻る

このエントリーをはてなブックマークに追加

この章の概要

この章の概要です。

ランダムシャッフル

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

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

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

良くない方法

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

#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)
{
	int a, b;
	size_t i;

	for(i = 0; i < size; ++i){
		a = rand() % size;
		b = rand() % size;
		SWAP( int, array[a], array[b] );
	}
}

/*
	配列の要素を出力
*/
void print_array(const int* array, size_t size)
{
	size_t i;

	for(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 というアルゴリズムが利用できます。

このアルゴリズムは、配列全体の中から1つの要素をランダムで選び出し、 これを末尾の要素と交換することを繰り返します。 ここで、"末尾" の位置は、交換を行うごとに1つずつ手前へ移動していきます。 言い換えれば、後ろの方から確定させていくということになります。

このアルゴリズムを実装すると、次のようになります。

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

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

forループは、配列の要素数-1回だけ繰り返されます。
配列の要素数が 10 だとすると、変数a は array[9]~array[1] を順番に参照するように変化していきます。 また、変数b は 0 <= b <= a ですから、 array[0]~array[9] まで、全要素が余すことなく、最低でも1回ずつは交換の対象になることが保証されています。 ですから、明らかに繰り返し回数が足りないということはなさそうです。 実際、この後で説明するように、Fisher-Yates shuffle の繰り返し回数は必要十分な量になっています。

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

偏り

Fisher-Yates shuffle の場合、良くない方法と比べて結果の偏り具合も改善されています。 配列の要素数が 3 しかないとしましょう。

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

この場合、ランダムシャッフル後の結果は、以下の 6通りのいずれかになります。 (順列の組み合わせなので、3! = 6 です)。

012
021
102
120
201
210

良くない方法の場合、交換する2つの要素の位置が、両方とも配列全体のどこかから選び出されます。 つまり、0~2 のどこかが選択されるので、選ばれる場所には 3通りの可能性がありますから、3 * 3 = 9通りの組み合わせがあります。 さらにこの交換処理を、配列の要素数分(=3) だけ繰り返しているので、93 = 729通りの結果が考えられます。
もちろん、ほとんどが同じ結果の重複になりますが、それは問題ではありません。 問題なのは、先ほどみた通り、ランダムシャッフルの結果は 6通りですが、729 % 6 をすると余り 3 が出るという点です。 余り 3 が出るということは、6通りの結果のうちのどこか 3つのパターンが出やすくなっているということです。 これが、結果が偏るという意味です。

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

ab
20
21
22

の 3通り。その次は、

ab
10
11

この 2通りです。

繰り返し回数は、配列の要素数 -1回ですから、この時点で処理は完了しています。 従って、3 * 2 = 6通りの可能性となります。 一応、すべての可能性を書き出すと次のようになります。

初回 b = 0, 2回目 b = 0120
初回 b = 0, 2回目 b = 1210
初回 b = 1, 2回目 b = 0201
初回 b = 1, 2回目 b = 1021
初回 b = 2, 2回目 b = 0102
初回 b = 2, 2回目 b = 1012

全6パターンがすべて表れています。 交換する要素の組み合わせは 6通り、結果のパターンも 6通りなので、すべて均等な確率であることが分かります。

ここで、すべて均等な確率だというのは理屈としてはその通りなのですが、 疑似乱数の生成に偏りがあれば、結局、多少の偏りが起こることになります。

まとめ

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

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

Fisher-Yates shuffle の実装は非常に簡単ですから、ランダムシャッフルの実装が必要な場面では、常にこの方法を使うのでも良いでしょう。 理論上、偏りの一切ない結果が得られます。
なお、Fisher-Yates shuffle の計算量は O(n) です。


練習問題

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


解答ページはこちら


参考リンク

更新履歴

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

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

'2014/1/22 誤植を修正。

'2012/5/19 新規作成。



前の章へ

次の章へ

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

Programming Place Plus のトップページへ