Java >> Java tutorial >  >> Tag >> java.util

Er java.util.Random virkelig så tilfældigt? Hvordan kan jeg generere 52! (faktorielle) mulige sekvenser?

java.util

At vælge en tilfældig permutation kræver samtidig mere og mindre tilfældighed end hvad dit spørgsmål antyder. Lad mig forklare.

Den dårlige nyhed:brug for mere tilfældighed.

Den grundlæggende fejl i din tilgang er, at den forsøger at vælge mellem ~2 226 muligheder ved at bruge 64 bits entropi (det tilfældige frø). For retfærdigt at vælge mellem ~2 226 muligheder, du bliver nødt til at finde en måde at generere 226 bits entropi i stedet for 64.

Der er flere måder at generere tilfældige bits på:dedikeret hardware, CPU-instruktioner, OS-grænseflader, onlinetjenester. Der er allerede en implicit antagelse i dit spørgsmål om, at du på en eller anden måde kan generere 64 bits, så bare gør hvad du ville, kun fire gange, og doner de overskydende bits til velgørenhed. :)

Den gode nyhed:brug for mindre tilfældighed.

Når du først har de 226 tilfældige bits, kan resten gøres deterministisk og dermed egenskaberne for java.util.Random kan gøres irrelevant . Sådan gør du.

Lad os sige, at vi genererer alle 52! permutationer (bær med mig) og sorter dem leksikografisk.

For at vælge en af ​​permutationerne behøver vi kun et enkelt tilfældigt heltal mellem 0 og 52!-1 . Det heltal er vores 226 bits entropi. Vi bruger det som et indeks i vores sorterede liste over permutationer. Hvis det tilfældige indeks er ensartet fordelt, er du ikke kun garanteret, at alle permutationer kan vælges, de vil blive valgt sandsynligvis (hvilket er en stærkere garanti end det, spørgsmålet stiller).

Nu behøver du faktisk ikke at generere alle disse permutationer. Du kan producere en direkte, givet dens tilfældigt valgte placering i vores hypotetiske sorterede liste. Dette kan gøres i O(n 2 ) tid ved at bruge Lehmer [1] kode (se også nummereringspermutationer og faktoriadisk talsystem). N'et her er størrelsen på dit dæk, dvs. 52.

Der er en C-implementering i dette StackOverflow-svar. Der er flere heltalsvariabler der, som ville løbe over for n=52, men heldigvis kan du i Java bruge java.math.BigInteger . Resten af ​​beregningerne kan transskriberes næsten som de er:

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] Ikke at forveksle med Lehrer. :)


Din analyse er korrekt:seeding af en pseudo-tilfældig talgenerator med et hvilket som helst specifikt frø skal give den samme sekvens efter en shuffle, hvilket begrænser antallet af permutationer, som du kan opnå til 2 64 . Denne påstand er let at verificere eksperimentelt ved at kalde Collection.shuffle to gange ved at sende en Random objekt initialiseret med det samme frø og observerer, at de to tilfældige blandinger er identiske.

En løsning på dette er altså at bruge en tilfældig talgenerator, der giver mulighed for et større frø. Java giver SecureRandom klasse, der kunne initialiseres med byte[] række af praktisk talt ubegrænset størrelse. Du kan derefter sende en forekomst af SecureRandom til Collections.shuffle for at fuldføre opgaven:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);

Generelt kan en pseudorandom number generator (PRNG) ikke vælge blandt alle permutationer på en liste med 52 elementer, hvis dens maksimale cykluslængde er mindre end 226 bit.

java.util.Random implementerer en algoritme med et modul på 2 48 og en maksimal cykluslængde på kun 48 bit, så meget mindre end de 226 bit, jeg nævnte. Du bliver nødt til at bruge en anden PRNG med en større cykluslængde, specifikt en med en maksimal cykluslængde på 52 factorial eller mere.

Se også "Blandet" i min artikel om generatorer af tilfældige tal.

Denne betragtning er uafhængig af PRNG'ens natur; det gælder ligeligt for kryptografiske og ikke-kryptografiske PRNG'er (selvfølgelig er ikke-kryptografiske PRNG'er upassende, når informationssikkerhed er involveret).

Selvom java.security.SecureRandom tillader frø af ubegrænset længde at blive sendt ind, SecureRandom implementering kunne bruge en underliggende PRNG (f.eks. "SHA1PRNG" eller "DRBG"). Og det afhænger af PRNG's maksimale cykluslængde, om den er i stand til at vælge blandt 52 ​​faktorielle permutationer.


Java tag