algorithm - fisher - ¿Qué es una buena baraja pseudoaleatoria de un solo paso?

fisher yates shuffle javascript

Question

La combinación aleatoria de Fisher-Yates proporciona un buen algoritmo para mezclar una matriz A de longitud n en una sola pasada:

For k = 1 to n
    Pick a random integer j from k to n
    Swap A[k] and A[j]

Después de una única pasada a través de este algoritmo, las entradas de A ocurren uniformemente al azar.

Una forma común de echar a perder este algoritmo es hacer lo siguiente:

For k = 1 to n
    Pick a random integer j from 1 to n
    Swap A[k] and A[j]

La distribución resultante de una sola pasada a través de este algoritmo no es uniformemente aleatoria, y hay una agradable discusión de lo que es en esta publicación: ¿Qué distribución obtienes de esta mezcla aleatoria desordenada?

Hace poco leí un delicioso artículo de Diaconis, Fulman y Holmes titulado Análisis de las máquinas barajadoras de casino donde los autores describen una máquina física que hace la siguiente mezcla de lotes:

For k = 1 to n
    Pick a random integer j from 1 to 10
    Randomly choose to place card k on the top or bottom of stack j

La pregunta que los autores abordan es si esto da un orden razonablemente aleatorio después de una sola pasada. La respuesta es decididamente no. Una forma de ver el error en esta barajadura es comenzar con una baraja de cartas que tenga n/2 tarjetas rojas encima de n/2 cartas negras. ¡El mazo resultante después de un solo pase tendrá como máximo 10 grupos de tarjetas rojas! Para n = 52*6 , esto no es terriblemente aleatorio. Los autores también muestran que una estrategia óptima de "adivinar la próxima carta" para el jugador una vez barajado, en promedio, adivinará correctamente 9.5 cartas, mientras que una estrategia óptima para un mazo aleatorio promediará solo 4.5 cartas correctamente adivinadas.

¿Hay otros barajamientos interesantes de un solo paso que logren casi aleatoriedad y / o distribuciones interesantes? Estoy especialmente interesado en barajas similares a las últimas que funcionan con lotes de entradas.

Answer 1

Si tienes un escritorio barajado, en el que deseas barajar un lote de cartas nuevas (y sabes que ninguna de las cartas está duplicada), entonces creo que lo siguiente es válido.

ForEach card in batch:
    gap = random(deck.size() + 1)  # choose a gap between cards, before first, or after last.
    deck.insertAt(gap,card)

Distribución

La distribución del azar es uniforme, y el orden de la baraja no cambia, por lo que es uniforme. Creo que el resultado debe ser uniforme. (Mis estadísticas están demasiado oxidadas para estar seguro).

Hora

Suponiendo que insertAt es O (1) no O (N) - que depende de la implementación de la plataforma - toda la rutina es O (tamaño de lote) - que es lo mejor que puede esperar, ya que tiene que manejar cada tarjeta.