¿Es java.util.Random realmente tan aleatorio? ¿Cómo puedo generar 52! posibles secuencias (factoriales)?

203

He estado usando Random (java.util.Random)para barajar un mazo de 52 cartas. Hay 52! (8.0658175e + 67) posibilidades. Sin embargo, descubrí que la semilla para java.util.Randomes a long, que es mucho más pequeña en 2 ^ 64 (1.8446744e + 19).

Desde aquí, sospecho si java.util.Random es realmente tan aleatorio ; ¿es realmente capaz de generar los 52! posibilidades?

Si no, ¿cómo puedo generar de manera confiable una mejor secuencia aleatoria que pueda producir los 52! posibilidades?

Serj Ardovic
fuente
21
"¿Cómo puedo generar un número aleatorio real de más de 52!" Los números de Randomnunca son números aleatorios reales . Es un PRNG, donde P significa "pseudo". Para números aleatorios reales , necesita una fuente de aleatoriedad (como random.org).
TJ Crowder
77
@JimGarrison Eso no es lo que busca OP. Está hablando de 10 ^ 68 posibles secuencias. Dado que cada secuencia pseudoaleatoria se identifica por su semilla, OP dice que podría haber como máximo 2 ^ 64 secuencias diferentes.
dasblinkenlight
66
Creo que es una pregunta interesante, y vale la pena pensarlo. Pero no puedo evitar preguntarme sobre el contexto de su problema: ¡qué es exactamente lo que está llevando al requisito de poder generar los 52! permutaciones? Por ejemplo, en el puente del mundo real podemos barajar el mazo y repartir una carta a la vez, sin embargo, solo hay ~ 6e11 manos diferentes, ya que muchas permutaciones diferentes resultan en la misma mano. Pensando en la otra dirección, ¿necesita una solución específica para 52! ¿O necesita una solución que generalice a, por ejemplo, dos barajas barajadas juntas (104! / (2 ** 52) posibilidades, o ~ 2e150)?
NPE
9
@NPE - Tome Solitario (Klondike) por ejemplo, 52! es exactamente el número de manos posibles ..
Serj Ardovic
3
Creo que esta es una lectura interesante: superuser.com/a/712583
Dennis_E

Respuestas:

153

Seleccionar una permutación aleatoria requiere simultáneamente más y menos aleatoriedad de lo que implica su pregunta. Dejame explicar.

La mala noticia: necesita más aleatoriedad.

La falla fundamental en su enfoque es que está tratando de elegir entre ~ 2 226 posibilidades utilizando 64 bits de entropía (la semilla aleatoria). Para elegir de manera justa entre ~ 2 226 posibilidades, tendrá que encontrar una manera de generar 226 bits de entropía en lugar de 64.

Hay varias formas de generar bits aleatorios: hardware dedicado , instrucciones de CPU , interfaces del sistema operativo , servicios en línea . Ya hay una suposición implícita en su pregunta de que de alguna manera puede generar 64 bits, así que solo haga lo que fuera a hacer, solo cuatro veces, y done el exceso de bits a la caridad. :)

La buena noticia: necesita menos aleatoriedad.

Una vez que tenga esos 226 bits aleatorios, el resto se puede hacer de manera determinista y, por lojava.util.Random tanto, las propiedades de pueden hacerse irrelevantes . Aquí es cómo.

¡Digamos que generamos los 52! permutaciones (tengan paciencia conmigo) y ordénelas lexicográficamente.

Para elegir una de las permutaciones, todo lo que necesitamos es un número entero aleatorio entre 0y 52!-1. Ese número entero son nuestros 226 bits de entropía. Lo usaremos como índice en nuestra lista ordenada de permutaciones. Si el índice aleatorio se distribuye de manera uniforme, no solo se garantiza que se puedan elegir todas las permutaciones, sino que se elegirán de manera equiprobable (lo cual es una garantía más sólida de lo que se plantea la pregunta).

Ahora, en realidad no necesitas generar todas esas permutaciones. Puede producir uno directamente, dada su posición elegida al azar en nuestra hipotética lista ordenada. Esto se puede hacer en tiempo O (n 2 ) usando el código Lehmer [1] (también vea las permutaciones de numeración y el sistema de numeración factorial ). El n aquí es el tamaño de su mazo, es decir, 52.

Hay una implementación de C en esta respuesta de StackOverflow . Hay varias variables enteras allí que se desbordarían para n = 52, pero afortunadamente en Java puede usar java.math.BigInteger. El resto de los cálculos se pueden transcribir casi como están:

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] No debe confundirse con Lehrer . :)

NPE
fuente
77
Je, y estaba seguro de que el enlace al final sería New Math . :-)
TJ Crowder
55
@TJCrowder: ¡Casi lo fue! Fueron los múltiples riemannianos infinitamente diferenciables que lo balancearon. :-)
NPE
2
Es bueno ver gente apreciando los clásicos. :-)
TJ Crowder
3
¿Dónde obtienes los 226 bits aleatorios en Java ? Lo sentimos, tu código no responde eso.
Thorsten S.
55
No entiendo lo que quieres decir, Java Random () tampoco proporcionará 64 bits de entropía. El OP implica una fuente no especificada que puede producir 64 bits para sembrar el PRNG. Tiene sentido suponer que puede pedirle a la misma fuente 226 bits.
Deja de dañar a Mónica el
60

Su análisis es correcto: sembrar un generador de números pseudoaleatorio con cualquier semilla específica debe producir la misma secuencia después de una combinación aleatoria, lo que limita el número de permutaciones que puede obtener a 2 64 . Esta afirmación es fácil de verificar experimentalmente llamando Collection.shuffledos veces, pasando un Randomobjeto inicializado con la misma semilla y observando que las dos mezclas aleatorias son idénticas.

Una solución a esto, entonces, es usar un generador de números aleatorios que permita una semilla más grande. Java proporciona una SecureRandomclase que podría inicializarse con una byte[]matriz de tamaño prácticamente ilimitado. Luego puede pasar una instancia de SecureRandoma Collections.shufflepara completar la tarea:

byte seed[] = new byte[...];
Random rnd = new SecureRandom(seed);
Collections.shuffle(deck, rnd);
dasblinkenlight
fuente
8
¡Seguramente, una semilla grande no es garantía de que todos los 52! se generarían posibilidades (¿de qué trata esta pregunta específicamente?) Como experimento mental, considere un PRNG patológico que toma una semilla arbitrariamente grande y genera una serie infinitamente larga de ceros. Parece bastante claro que el PRNG necesita satisfacer más requisitos que simplemente tomar una semilla lo suficientemente grande.
NPE
2
@SerjArdovic Sí, cualquier material semilla pasado a un objeto SecureRandom debe ser impredecible, según la documentación de Java.
dasblinkenlight
10
@NPE Tiene razón, aunque una semilla demasiado pequeña es una garantía del límite superior, una semilla lo suficientemente grande no está garantizada en el límite inferior. Todo lo que hace es eliminar un límite superior teórico, ¡haciendo posible que el RNG genere los 52! combinaciones.
dasblinkenlight
55
@SerjArdovic El número más pequeño de bytes requerido para eso es 29 (¡necesita 226 bits para representar 52! Combinaciones de bits posibles, que son 28.25 bytes, por lo que debemos redondearlo). Tenga en cuenta que el uso de 29 bytes de material semilla elimina el límite superior teórico sobre el número de mezclas que puede obtener, sin establecer el límite inferior (vea el comentario de NPE sobre un RNG horrible que toma una semilla muy grande y genera una secuencia de todos los ceros).
dasblinkenlight
8
La SecureRandomimplementación seguramente usará un PRNG subyacente. Y depende del período de ese PRNG (y en menor medida, la duración del estado) si es capaz de elegir entre 52 permutaciones factoriales. (Tenga en cuenta que la documentación dice que la SecureRandomimplementación "cumple mínimamente" ciertas pruebas estadísticas y genera resultados que "deben ser criptográficamente fuertes", pero no establece un límite inferior explícito en la duración del estado del PRNG subyacente o en su período).
Peter O.
26

En general, un generador de números pseudoaleatorios (PRNG) no puede elegir entre todas las permutaciones de una lista de 52 elementos si su longitud de estado es inferior a 226 bits.

java.util.Randomimplementa un algoritmo con un módulo de 2 48 ; por lo tanto, su longitud de estado es de solo 48 bits, mucho menos que los 226 bits que mencioné. Deberá usar otro PRNG con una longitud de estado mayor, específicamente, uno con un período de 52 factorial o mayor.

Ver también "Barajar" en mi artículo sobre generadores de números aleatorios .

Esta consideración es independiente de la naturaleza del PRNG; se aplica igualmente a los PRNG criptográficos y no criptográficos (por supuesto, los PRNG no criptográficos son inapropiados siempre que se trate de seguridad de la información).


Aunque java.security.SecureRandompermite pasar semillas de longitud ilimitada, la SecureRandomimplementación podría usar un PRNG subyacente (por ejemplo, "SHA1PRNG" o "DRBG"). Y depende del período de ese PRNG (y en menor medida, la duración del estado) si es capaz de elegir entre 52 permutaciones factoriales. (Tenga en cuenta que defino "longitud de estado" como el "tamaño máximo de la semilla que un PRNG puede tomar para inicializar su estado sin acortar o comprimir esa semilla ").

Peter O.
fuente
18

Permítanme disculparme de antemano, porque esto es un poco difícil de entender ...

En primer lugar, ya sabes que java.util.Randomno es completamente aleatorio en absoluto. Genera secuencias de una manera perfectamente predecible a partir de la semilla. Tiene toda la razón en que, dado que la semilla tiene solo 64 bits de longitud, solo puede generar 2 ^ 64 secuencias diferentes. Si de alguna manera generara 64 bits aleatorios reales y los usara para seleccionar una semilla, no podría usar esa semilla para elegir aleatoriamente entre todos de los 52! posibles secuencias con igual probabilidad.

Sin embargo, este hecho no tiene ninguna consecuencia , siempre y cuando no vayas a generar más de 2 ^ 64 secuencias, siempre que no haya nada 'especial' o 'notablemente especial' sobre las secuencias 2 ^ 64 que pueda generar .

Digamos que tenía un PRNG mucho mejor que utilizaba semillas de 1000 bits. Imagine que tiene dos formas de inicializarlo: una forma lo inicializaría utilizando toda la semilla, y una forma la reduciría a 64 bits antes de inicializarla.

Si no sabía qué inicializador era cuál, ¿podría escribir algún tipo de prueba para distinguirlos? A menos que haya tenido la (des) suerte de terminar inicializando al malo con el mismo 64 bits dos veces, la respuesta es no. No podría distinguir entre los dos inicializadores sin un conocimiento detallado de alguna debilidad en la implementación específica de PRNG.

Alternativamente, imagine que el Random clase tenía una matriz de 2 ^ 64 secuencias que se seleccionaron completamente y al azar en algún momento en el pasado distante, y que la semilla era solo un índice en esta matriz.

Entonces, el hecho de que Randomuse solo 64 bits para su semilla no es necesariamente un problema estadístico, siempre que no haya una posibilidad significativa de que use la misma semilla dos veces.

Por supuesto, para propósitos criptográficos , una semilla de 64 bits simplemente no es suficiente, porque hacer que un sistema use la misma semilla dos veces es computacionalmente factible.

EDITAR:

Debo agregar que, a pesar de que todo lo anterior es correcto, la implementación real java.util.Randomno es asombrosa. Si está escribiendo un juego de cartas, tal vez use la MessageDigestAPI para generar el hash SHA-256 "MyGameName"+System.currentTimeMillis()y use esos bits para barajar el mazo. Según el argumento anterior, siempre y cuando sus usuarios no estén jugando realmente, no tiene que preocuparse porque eso currentTimeMillisregrese mucho tiempo. Si los usuarios están realmente el juego, a continuación, utilizar SecureRandomsin semilla.

Matt Timmermans
fuente
66
@ThorstenS, ¿cómo podrías escribir algún tipo de prueba que pueda determinar que hay combinaciones de cartas que nunca pueden aparecer?
Matt Timmermans
2
Hay varias suites de prueba de números aleatorios como Diehard de George Marsaglia o TestU01 de Pierre L'Ecuyer / Richard Simard que encuentran fácilmente anomalías estadísticas en la salida aleatoria. Para la comprobación de tarjetas puede usar dos cuadrados. Usted determina el orden de la tarjeta. La primera casilla muestra la posición de las dos primeras cartas como par xy: la primera carta como xy la posición de diferencia (!) (-26-25) de la segunda carta como y. La segunda casilla muestra la tercera y cuarta carta con (-25-25) en relación con la segunda / tercera. Esto mostrará de inmediato brechas y grupos en su distribución si lo ejecuta por un tiempo.
Thorsten S.
44
Bueno, esa no es la prueba que dijiste que podrías escribir, pero tampoco es aplicable. ¿Por qué supone que hay brechas y grupos en la distribución que tales pruebas descubrirían? Eso implicaría una "debilidad específica en la implementación de PRNG" como mencioné, y no tiene nada que ver con la cantidad de semillas posibles. Tales pruebas ni siquiera requieren que reinicies el generador. Al principio advertí que esto era difícil de entender.
Matt Timmermans
3
@ThorstenS. Esos conjuntos de pruebas no determinarán en absoluto si su fuente es un PRNG criptográficamente seguro de 64 bits o un verdadero RNG. (Después de todo, para lo que sirven esas suites es probar las PRNG). Incluso si conociera el algoritmo en uso, una buena PRNG hace inviable determinar el estado sin una búsqueda de fuerza bruta del espacio de estados.
Sneftel
1
@ThorstenS .: En una baraja de cartas real, la gran mayoría de las combinaciones nunca aparecerán. Simplemente no sabes cuáles son esos. Para un PRNG medio decente es lo mismo: si puede probar si una secuencia de salida dada durante tanto tiempo está en su imagen, eso es un defecto en el PRNG. ¡Estado / período ridículamente enorme como 52! no es necesario; 128 bits debería ser suficiente.
R .. GitHub DEJA DE AYUDAR AL HIELO
10

Voy a tomar un poco de una táctica diferente en esto. Está en lo cierto: ¡su PRNG no podrá alcanzar los 52! posibilidades

La pregunta es: ¿cuál es la escala de su juego de cartas?

Si estás haciendo un juego simple al estilo klondike? ¡Entonces definitivamente no necesitas los 52! posibilidades En cambio, míralo así: un jugador tendrá 18 quintillones de juegos distintos. Incluso teniendo en cuenta el "Problema del cumpleaños", tendrían que jugar miles de millones de manos antes de encontrarse con el primer juego duplicado.

Si estás haciendo una simulación monte-carlo? Entonces probablemente estés bien. Es posible que tenga que lidiar con artefactos debido a la 'P' en PRNG, pero probablemente no se encontrará con problemas simplemente debido a un espacio de semilla bajo (nuevamente, está viendo quintillones de posibilidades únicas). Por otro lado, si está trabajando con un gran recuento de iteraciones, entonces, su bajo espacio inicial puede ser un factor decisivo.

Si estás haciendo un juego de cartas multijugador, especialmente si hay dinero en juego? Luego, tendrás que buscar en Google cómo los sitios de póker en línea manejaron el mismo problema que estás preguntando. Porque si bien el problema de poco espacio inicial no es perceptible para el jugador promedio, es explotable si vale la pena invertir tiempo. (Todos los sitios de póker pasaron por una fase en la que sus PRNG fueron 'pirateados', dejando que alguien vea las cartas ocultas de todos los demás jugadores, simplemente deduciendo la semilla de las cartas expuestas). Si esta es la situación en la que se encuentra, no 't simplemente encontrar un mejor PRNG - que necesita para tratarlo tan seriamente como un problema Crypto.

Kevin
fuente
9

Solución corta que es esencialmente la misma de dasblinkenlight:

// Java 7
SecureRandom random = new SecureRandom();
// Java 8
SecureRandom random = SecureRandom.getInstanceStrong();

Collections.shuffle(deck, random);

No necesita preocuparse por el estado interno. Larga explicación de por qué:

Cuando creas un SecureRandom instancia de esta manera, accede a un generador de números aleatorios verdaderos específicos del sistema operativo. Este es un grupo de entropía donde se accede a valores que contienen bits aleatorios (por ejemplo, para un temporizador de nanosegundos, la precisión de nanosegundos es esencialmente aleatoria) o un generador interno de números de hardware.

Esta entrada (!) Que aún puede contener rastros espurios se alimenta a un hash criptográficamente fuerte que elimina esos rastros. ¡Esa es la razón por la que se usan esos CSPRNG, no para crear esos números ellos mismos! El SecureRandomtiene un contador que traza la cantidad de bits utilizado ( getBytes(), getLong()etc.) y recargas de la SecureRandomcon los bits de entropía cuando sea necesario .

En resumen: simplemente olvide las objeciones y úselas SecureRandomcomo un verdadero generador de números aleatorios.

Thorsten S.
fuente
4

Si considera el número solo como una matriz de bits (o bytes), entonces tal vez podría usar las Random.nextBytessoluciones (seguras) sugeridas en esta pregunta de desbordamiento de pila y luego mapear la matriz en a new BigInteger(byte[]).

IvanK
fuente
3

Un algoritmo muy simple es aplicar SHA-256 a una secuencia de enteros que incrementen de 0 en adelante. (Se puede agregar una sal si se desea para "obtener una secuencia diferente"). Si suponemos que la salida de SHA-256 es "tan buena como" enteros distribuidos uniformemente entre 0 y 2 256 - 1, entonces tenemos suficiente entropía para el tarea.

Para obtener una permutación de la salida de SHA256 (cuando se expresa como un número entero) uno simplemente necesita reducirlo en los módulos 52, 51, 50 ... como en este pseudocódigo:

deck = [0..52]
shuffled = []
r = SHA256(i)

while deck.size > 0:
    pick = r % deck.size
    r = floor(r / deck.size)

    shuffled.append(deck[pick])
    delete deck[pick]
Artelius
fuente