Es java.útil.Al azar realmente al azar? ¿Cómo puedo generar 52! (factorial) ¿posibles secuencias?

Su análisis es correcto: sembrar un generador de números pseudo-aleatorios con cualquier semilla específica debe producir la misma secuencia después de un barajamiento, limitando el número de permutaciones que podría obtener para 2⁶⁴. Esta aserción es fácil de verificar experimentalmente llamando a Collection.shuffle dos veces, pasando un objeto Random inicializado con la misma semilla, y observando que los dos barajamientos aleatorios son idénticos.

Una solución a esto, entonces, es usar un generador de números aleatorios que permite una semilla más grande. Java proporciona SecureRandom clase que podría ser inicializada con byte[] array de tamaño virtualmente ilimitado. Entonces puedes pasar una instancia de SecureRandom a Collections.shuffle para completar la tarea:

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

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.Random implementa un algoritmo con un módulo de 2⁴⁸; por lo tanto, su longitud de estado es de solo 48 bits, mucho menos que los 226 bits a los que me referí. Necesitará usar otro PRNG con una longitud de estado mayor, específicamente, uno con un período de 52 factoriales o mayor.

Ver también " Elegir entre Todos Permutaciones " 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 cifrados (por supuesto, los PRNG no cifrados son inapropiados cuando la seguridad de la información está involucrada).

Aunque java.security.SecureRandom permite que se pasen semillas de longitud ilimitada, la implementación SecureRandom podría usar un PRNG subyacente (por ejemplo, "SHA1PRNG" o "DRBG"). Y depende de que PRNG período (y en menor medida, longitud 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").

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

En primer lugar, ya sabes que java.util.Random no es completamente aleatorio. Genera secuencias de forma perfectamente predecible desde la semilla. Usted está completamente en lo correcto que, dado que la semilla tiene solo 64 bits de largo, 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 es de ninguna consecuencia siempre y cuando en realidad no vas a generar más de 2^64 secuencias, siempre y cuando no haya nada 'especial' o 'notablemente especial' sobre las 2^64 secuencias que puede generar.

Digamos que tenías un PRNG mucho mejor que usaba semillas de 1000 bits. Imagina que tienes dos formas de inicializarlo one una forma de inicializarlo usando toda la semilla, y una forma sería hash la semilla hasta 64 bits antes de inicializarlo.

Si no sabías qué inicializador era cuál, ¿podrías escribir algún tipo de prueba para distinguirlos? A menos que haya tenido (des) la suerte de terminar inicializando el malo con el mismo 64 bits dos veces, entonces 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 la clase Random tenía una matriz de 2^64 secuencias que fueron seleccionadas completamente y al azar en algún momento en el pasado distante, y que la semilla era solo un índice en esta matriz.

Así que el hecho de que Random use solo 64 bits para su semilla es en realidad no necesariamente un problema estadísticamente, siempre y cuando 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 no es suficiente, porque obtener un sistema para usar la misma semilla dos veces es computacionalmente factible.

EDITAR:

Debo añadir que, aunque todo lo anterior es correcto, que la ejecución real de java.util.Random no es impresionante. Si está escribiendo un juego de cartas, puede usar la API MessageDigest para generar el hash SHA-256 de "MyGameName"+System.currentTimeMillis(), y usar esos bits para barajar el mazo. Por el argumento anterior, siempre y cuando sus usuarios no están jugando realmente, usted no tiene que preocuparse de que currentTimeMillis devuelve un largo. Si sus usuarios son realmente el juego, a continuación, utilizar SecureRandom sin semilla.

Voy a tomar un poco de una táctica diferente en esto. Tienes razón en tus suposiciones - su PRNG no va a ser capaz de golpear a todos los 52! posibilidad.

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

Si estás haciendo un simple juego al estilo klondike? Entonces definitivamente no necesitas los 52! posibilidad. En su lugar, míralo así: un jugador tendrá 18 quintillones partidas distintas. 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 de Monte Carlo?, Entonces estás , probablemente 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 semillas bajo (de nuevo, está buscando quintillones de posibilidades únicas. Por otro lado, si estás trabajando con un gran número de iteraciones, entonces, sí, tu bajo espacio de semillas podría romper el trato.

Si usted está haciendo un juego de cartas multijugador, sobre todo si hay dinero en juego? Entonces usted va a tener que hacer un poco de búsqueda en Google sobre cómo los sitios de póquer en línea manejado el mismo problema que usted está preguntando. Porque si bien el problema del espacio de semillas bajo no es notable para el jugador promedio, es explotable si vale la pena la inversión de tiempo. (Los sitios de poker todos pasaron por una fase donde sus PRNGs fueron 'hackeados', dejando que alguien vea las cartas de mano de todos los otros jugadores, simplemente deduciendo la semilla de las cartas expuestas.) Si esta es la situación en la que se encuentra, no simplemente encuentre un mejor PRNG, deberá tratarlo tan seriamente como un problema de Cripto.

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 tienes que preocuparte por el estado interno. Explicación larga por qué:

Cuando crea una instancia SecureRandom de esta manera, accede a un sistema operativo específico verdadero generador de números aleatorios. Esto es un pool de entropía donde los valores son que contienen bits aleatorios (por ejemplo, para un temporizador de nanosegundos el nanosegundo la precisión es esencialmente aleatoria) o un número de hardware interno generador.

Esta entrada!) que todavía pueden contener trazas espurias se alimentan en un hash criptográficamente fuerte que elimina esos rastros. ¡Esa es la razón por la que se usan esos CSPRNGs, no para crear esos números ellos mismos! El SecureRandom tiene un contador que rastrea cuántos bits se utilizaron (getBytes(), getLong() etc.) y rellena el SecureRandom con bits de entropía cuando sea necesario.

En resumen: Simplemente olvídese de las objeciones y use SecureRandom como verdadero generador de números aleatorios.

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

Un algoritmo muy simple es aplicar SHA-256 a una secuencia de enteros que se incrementan desde 0 hacia arriba. (Se puede añadir una sal si se desea para "obtener una secuencia diferente".) Si asumimos que la salida de SHA-256 es" tan buena como " números enteros uniformemente distribuidos entre 0 y 2²⁵⁶ - 1 entonces tenemos suficiente entropía para la tarea.

Para obtener una permutación de la salida de SHA256 (cuando se expresa como un entero) uno simplemente necesita reducirla módulo 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]