[解決済み】java.util.Randomは本当にランダムなのか？どうやったら52! (階乗)可能な配列を生成することができますか？

質問

私はこれまで Random (java.util.Random) を使って、52枚のカードのデッキをシャッフルしています。その数、なんと52枚 (8.0658175e+67) の可能性があります。それなのに、種明かしをすると java.util.Random は long となり、2^64 (1.8446744e+19)とかなり小さくなります。

ここから、怪しいのは java.util.Random は本当にランダムなのか 52の可能性をすべて生み出すことができるのでしょうか？

そうでない場合、どうすればより良い乱数列を確実に生成し、52!通りの可能性を生み出すことができるでしょうか?

どのように解決するのですか？

ランダムな並べ替えを選択するためには、質問者が示唆するよりも多くのランダム性と少ないランダム性が同時に必要です。説明しましょう。

悪い知らせ：もっとランダム性が必要。

あなたのアプローチの根本的な欠点は、～2つのうちどちらかを選ぼうとしていることです。 ²²⁶ 64ビットのエントロピー（乱数種）を使って、可能性があります。2つの可能性を公平に選択するために ²²⁶ 64ビットの代わりに226ビットのエントロピーを生成する方法を見つけなければならないのです。

ランダムビットを生成する方法はいくつかあります。 専用ハードウェア , CPU命令 , OSインターフェース , オンラインサービス . あなたの質問には、どうにかして64ビットを生成できるという暗黙の前提がすでにあるので、あなたがしようとしていたことを4回だけ行い、余ったビットを慈善団体に寄付しましょう。）

良い点：ランダム性を少なくする必要がある。

この226個のランダムビットがあれば、あとは決定論的に行うことができますので のプロパティは java.util.Random は無関係にすることができる . 以下はその方法です。

52！の順列をすべて生成し（我慢してください）、辞書順に並べたとしましょう。

順列の1つを選択するために必要なのは、以下の間の1つのランダムな整数だけです。 0 と 52!-1 . この整数が226ビットのエントロピーです。これを並べ替えのインデックスとして使用する。ランダムインデックスが一様に分布していれば、すべての並べ換えが選択されることが保証されるだけでなく、選択されることになります。 等速 (これは質問の内容よりも強い保証です)。

さて、実際にはこれらの並べ換えをすべて生成する必要はありません。この仮想的な並べ替えリストの中でランダムに選ばれた位置から、直接並べ替えを生成することができます。これは、O(n ² ) の時間を使って レーマー ^[1] コード (また ナンバリングパーミュテーション と ファクトリアディック数体系 ). ここでいうnはデッキの大きさ、つまり52です。

C言語の実装は、この StackOverflowの回答 . そこには、n=52 でオーバーフローしてしまういくつかの整数変数がありますが、幸いにも Java では java.math.BigInteger . 残りの計算は、ほぼそのまま書き写すことができます。

public static int[] shuffle(int n, BigInteger random_index) {
    int[] perm = new int[n];
    BigInteger[] fact = new BigInteger[n];
    fact[0] = BigInteger.ONE;
    for (int k = 1; k < n; ++k) {
        fact[k] = fact[k - 1].multiply(BigInteger.valueOf(k));
    }

    // compute factorial code
    for (int k = 0; k < n; ++k) {
        BigInteger[] divmod = random_index.divideAndRemainder(fact[n - 1 - k]);
        perm[k] = divmod[0].intValue();
        random_index = divmod[1];
    }

    // readjust values to obtain the permutation
    // start from the end and check if preceding values are lower
    for (int k = n - 1; k > 0; --k) {
        for (int j = k - 1; j >= 0; --j) {
            if (perm[j] <= perm[k]) {
                perm[k]++;
            }
        }
    }

    return perm;
}

public static void main (String[] args) {
    System.out.printf("%s\n", Arrays.toString(
        shuffle(52, new BigInteger(
            "7890123456789012345678901234567890123456789012345678901234567890"))));
}

^[1] と混同しないように レーラー . :)