前回のクイズ シャッフル、ですが、今気づけば肝心の問題の部分が何か、が良くわからない状態になっていました。大変失礼いたしました。もう一度問題をご紹介します。

シャッフル／シャッフル／シャッフル

public class Shuffle {
  public static <T> void shuffle(T[] a) {
    Random r = new Random();
    for (int i = 0; i < a.length; i++) {
      int j = r.nextInt(a.length);
      int k = r.nextInt(a.length);

      swap(a, j, k);
    }
  }
  public static <T> void swap(T[] a, int i, int j) {
    if (i != j) {
      T tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }
  }
}

こ のプログラムは配列の内容をランダムに再配置するというプログラムです。ためしに Integer[] a = {1, 2, 3} という配列をこのプログラムを使って6,000回シャッフルし、その組み合わせの出現数を数えてみると次のようになりました。

[1, 2, 3]=1129, [1, 3, 2]=1029, [2, 1, 3]=1021, [2, 3, 1]=853, [3, 1, 2]=886, [3, 2, 1]=1082}

さて、この結果から判断できるのは次の4つのうちどれでしょうか。

• (1) 乱数なのでこの程度の偏りは偶然。もう一度実行すると別のパターンに偏る。
• (2) java.util.Random の乱数は周期性があるので、特定のパターンに偏りが出る。
• (3) java.util.Random の代わりに java.security.SecureRandom を使うと偏りは小さくなる。
• (4) このアルゴリズムでは常に特定のパターンに偏る。