Macromedia Flash非公式テクニカルノート

配列を偏りなくランダムに並替える

ID: FN0212003 Product: Flash

Platform: All
Version: 5.0 and Above

[*注] ActionScript 3.0にもとづくスクリプトと解説は「配列を偏りなくランダムに並べ替える」をご参照ください。

1. 配列をランダムに並替える
'配列をランダムに並替えるユーザー定義関数('function')を考えてみましょう。

// function定義: xShuffleArray
// 引数: 配列
// 戻り値: なし
function xShuffleArray(l_array) {  //[1]'function'定義
  var n = l_array.length;  //[2]配列の長さを取得
  var i = n;
  while (i--) {  //[3]配列エレメントすべてをループ処理
    var j = Math.floor(Math.random()*n);  //[4]ランダムなインデックスを計算
    // [5]対象エレメントをランダムなインデックスと入替え
    var t = l_array[i];
    l_array[i] = l_array[j];
    l_array[j] = t;
  }
}

[1]配列をランダムに並替えるユーザー定義関数('function')xShuffleArrayを定義します。ランダムに並替える対象となる配列を、引数として渡します。引数の配列自体を並替えますので、戻り値はありません。

[2]まず配列の長さを取得します。エレメントの数をもとに、取出すランダムな位置のインデックス番号を計算するためです。同じ値を、ローカル変数nとiに代入します。変数iの値は、後の処理で変化します。変数nの値は、終始変わりません。

[3]配列のエレメントすべてをループ処理します。ループ条件は、論理式でなく変数iになっています。変数が数値の場合、0以外の値は'true'と評価されます。変数iの値は、ポストデクリメントで、評価後に1減算されます。したがって、エレメント数と同じ回数の処理が行われることになります。

[4]並替える対象となるインデックス番号を、ランダムに決定します。返される値は、0からnまでの整数です。変数nの値は配列の長さで、配列の最後のエレメントのインデックスより1大きいです。したがって、0から最後のインデックス番号までの値が、ランダムで返されます。

[5]配列の最後のエレメントから順に抜出して、ランダムに決められたインデックス番号のエレメントと差替えていきます。変数iの初期値は配列の長さで、'while'アクションの評価後にポストデクリメントi--で1減算しています。ですから、最後のエレメントから最初のエレメントまで、さかのぼってすべて処理することになります。

2. 並替えの偏り
1.のスクリプトは、問題がないように見えます。実際、配列を引数にして並替えてみると、順序はランダムになります。けれども、このスクリプトの並替えには偏りがあります。

このスクリプトでは、毎回最大値が最終インデックス番号までのランダムな整数を計算しています。配列の長さ(エレメント数)が3だとすると、0から2までの整数を毎回ランダムに出す訳です。このとき得られる整数は、0、1、2の3通りです。

3通りのランダムな整数値を使ってエレメント数と同じ3回順序の入替えを行った場合、その並替えの結果は3×3×3=27通りになります。ところが、3つの値のすべての並び順のパターンつまり順列は、3×2×1=6通りです。27は6で割切れず、3余りが出ます。つまり、27通りの中には、他の並び順より多く発生しているパターンが3通りあるということです(後述「参考」を参照)。

3. 偏りのない並替え
偏りのない並替えを行うには、前述の順列の考え方と同じく、ランダムな整数の最大値を毎回減算すればよいです。この修正を行ったのが、以下のスクリプトです。

// function定義: xShuffleArray
// 引数: 配列
// 戻り値: なし
function xShuffleArray(l_array) {
  var i = l_array.length;
  while (i--) {
    var j = Math.floor(Math.random()*(i+1));  //ランダムなインデックスを計算
    var t = l_array[i];
    l_array[i] = l_array[j];
    l_array[j] = t;
  }
}

変更したのは、ランダムなインデックスの計算を行うステートメントです。変数iを元にしますので、発生するランダムな整数の最大値が、処理とともに減少します。

この考え方は、カードのシャッフルと同じです。カードをまとめて手にしたら、好きな位置から1枚抜いてテーブルの上に重ねます。つぎのカードも同じように、1枚抜いてはテーブルのカードに積重ねます。それを繰返して、手に残った最後の1枚をテーブルの山の一番上に重ね終わったとき、ランダムに並替えたカードの山ができあがる訳です。

この場合手元のカードは、テーブルに積み重ねるたびに、1枚ずつ減っていきます。ですから、ランダムなインデックスの最大値も、同様に減らすことになります。ランダムに取出したカードはテーブルに積んで、手元のカードに戻さないことにより、すべてのカードを漏れなく処理したことになるのです。

参考
1.のスクリプトのロジックで、["a", "b", "c"]の3エレメントの配列を並替えた場合に、発生する27パターンをシミュレートしてみました(ただし並替えは、スクリプトとは逆に、先頭から行っています)。順列6通りの内、半分のパターンが4回、残りの半分が5回発生しています(シミュレーションですので、Flashの処理で実際にどのパターンが多く発生するかは別論とします)。

No. 並替えのパターン
1 c a b
2 b c a
3 b a c
4 c b a
5 a c b
6 a b c
7 b c a
8 a b c
9 a c b
10 c b a
11 a c b
12 a b c
13 c a b
14 b c a
15 b a c
16 a c b
17 b a c
18 b c a
19 a c b
20 b a c
21 b c a
22 a b c
23 c a b
24 c b a
25 b a c
26 c b a
27 c a b

_____

作成者: 野中文雄
更新日: 2011年10月11日「配列を偏りなくランダムに並べ替える」へのリンクを追加。
協力者: rio
作成日: 2002年12月15日


Copyright © 2001-2006 Fumio Nonaka.  All rights reserved.