El algoritmo de Fisher-Yates (o alguna variante del mismo), es el que se usa típicamente para barajar en los juegos de azar.
También es el algoritmo que permite recorrer toda una selección (por ejemplo una lista musical), de forma aleatoria una sola vez (una reproducción por cada elemento en la lista). Ver más detalles en la sección más abajo.
El algoritmo Fisher-Yates, es un algoritmo de permutaciones que técnicamente encaja en la categoría de los algoritmos de ordenamiento, aunque en este caso, el fin perseguido es el opuesto, desordenar los ítems que contiene. Y por tanto debería constar en las bibliotecas de ordenamiento como Random Sort al menos.
El algoritmo Fisher-Yates, aparece por primera vez documentado por Ronald A. Fisher y Frank Yates, en el libro titulado Statistical tables for biological, agricultural and medical research. si bien su descripción era realizada con lápiz y papel.
Posteriormente otros autores (probablemente sin conocimiento previo de dicha publicación) elaboraron el mismo algoritmo. Lincoln E. Moses y Robert V. Oakford en Tables of Random Permutations y Durstenfeld en CACM-7(1964), a quienes Knuth cita en su libro The Art of Computer Programming y que describe como "Algoritmo P" (pags. 139-140 del Vol.2).
En la 'sabiduría popular' este algoritmo, se conoce como el 'barajado del sombrero', ya que la descripción que Fisher y Yates hicieron de él, es la que comúnmente se lleva a cabo cuando se hace una rifa, por ejemplo (ver los detalles más abajo, en la descripción del mismo).
Fue Durstenfeld, quien primero hizo una transcripción en la forma de algoritmo para usarse en un ordenador. La descripción de Fisher y Yates, exige el uso de 2 matrices (en los trabajos de campo, es simplemente anotar en dos partes de un papel, aunque bien podría reutilizarse borrando y rescribiendo en el mismo sitio), Durstenfeld usa la propia matriz, para llevar a cabo todo el algoritmo, necesitando solo como memoria extra una variable temporal.
La forma más simple de entenderlo es partir de la forma popular:
Se repiten estos 3 pasos, hasta que solo quede 1, en la línea de arriba sin tachar, entonces se toma directamente y se pasa a la de abajo.
Es un error común pensar que la aleatoriedad de la lista es dependiente del algoritmo de barajado (siempre que sea correcto, que para cada posición sea elegida una posición al azar), cuando en realidad es dependiente del algoritmo de aleatoriedad/pseudoaleatoriedad. La lista simplemente es reordenada de otra manera, siempre contiene los mismos valores, solo cambian sus posiciones, que son dependientes del algoritmo de aleatoriedad (que no se está implementando, en ningún caso). En cualquier caso, una vez construido el algoritmo, puede o debe probarse su imparcialidad demostrando las desviaciones de probabilidad.
Ésta es la descripción del algoritmo de Durstenfeld. Debe notarse que el elemento que queda al final del recorrido (ítem-0) como entrada, es el primero en la salida, razón por la que no necesita ser intercambiado de posición (es la misma).
Aunque el coste (en tiempo y memoria) sea mayor, el mismo algoritmo tendría el siguiente pseudocódigo resuelto con una estructura que permita inserciones y eliminaciones en posiciones arbitrarias:
Es interesante observar en este caso, que los ítems al añadirlos al final, lo hacen a la derecha del añadido anterior, es decir tal como Fisher y Yates describieron. Si se prefiere, conservar un añadido a la izquierda del previo añadido (tal como en el caso mostrado del array), debe cambiarse la línea de añadido, por la siguiente:
Puesto que el bucle hace un recorrido regresivo, k vale justo 1 más de la posición límite pedida a la función Random, y se añade justo antes de que sea eliminado el elemento elegido, por tanto k irá siendo siempre un valor menor en cada ciclo, por lo que en efecto se iría colocando a la izquierda del previo. Esto se puede ver más claro, en los ejemplos paso a paso, en la sección correspondiente (más abajo).
Fue publicado en 1986 en IPL-22, por Sattolo en Information Processing Letters y tiene algunas particularidades que se describen:
Hay algunas variaciones que pueden ser aplicadas a todas las implementaciones comentadas hasta el momento, bien que pueda variar el código exacto que deba añadirse o modificarse en cada una. Implementar estas variaciones, implica añadir parámetros en las funciones para que al invocarlas puede elegirse el valor necesario para que cumpla la misión encomendada.
Supongamos una baraja de 52 cartas y supongamos que queremos que cada 13 cartas que baraje, se salte 3. Siendo el array de 0 a 51 elementos, en las posiciones k módulo 13 (que son 0, 13, 26 y 39) al llegar a dichas posiciones aumentará k en 3 unidades, que en efecto tiene como consecuencia no barajar 3 elementos seguidos, como son 4 veces (4 grupos de 13) hay 12 barajados menos. También pueden especificarse los parámetros como los que se omiten y los que se barajan (en el ejemplo, serían Barajan=10 y se Omiten=3) y la suma de ambos sería el equivalente al grupo, así se evita la necesidad de comprobar que salto sea menor que grupo.
Debe notarse que esta variación no evita que los valores en esas posiciones se mantenga en su mismo sitio (pueden salir elegidas por la función Random en cualquier otro instante del recorrido del bucle), pero si tiene por efecto, que 12 elementos de los 52 no sean barajados, lo que por supuesto tendrá incidencia, en una cierta similitud entre la serie a la salida y la serie de entrada.
Imagínese un mazo de 28 cartas, y bloques de 4 cartas, lo que nos daría 7 montones y sería equivalente a barajar una serie de 7 elementos (7 * 4 = 28), si los montones fueran de 6 cartas el último montón solo tendría 4 cartas, luego cuando saliera éste solo se intercambiarían 4 cartas con el bloque que se intercambia. Se pone una serie de resultados de 28 elementos, con un bloque de 4, para darse cuenta como el afecta a un barajado de esta manera. Obsérveses como las tuplas de 4 elementos (se ha coloreado un par de ellas), no cambian entre sí el orden (de sus elementos):
Si el bloque produce grupos exactos entonces no generará todas las permutaciones posibles, de hecho ni aunque haya bloques no exactos, no generará todas las permutaciones posibles. Por ejemplo para una serie de 7 elementos (que permite 5040 permutaciones distintas de la serie) con un bloque de 2 genera 144 permutaciones, con un bloque de 3 genera sólo 12 permutaciones, con un bloque de 4, 5 y 6 solo hay 2 permutaciones posibles (ya que solo ofrece 2 grupos). Por ello hay que considerar que el número de permutaciones obedece más al número de grupos y los elementos en el último grupo, que a la cantidad de elementos. Por último, señalar que si el tamaño de bloque es 1, equivale a barajar todos los ítems, cual si no se usara dicha funcionalidad. Hay que considerar que la entrada y la salida varían poco entre sí, pero dado que tras la salida hay un nuevo juego, la siguiente entrada tendrá una permutación muy distinta de la salida previa. Si el caso es que se desea que haya una mayor posibilidad de permutaciones, podría barajarse el último bloque (que antes estaba en otra posición y se intercambió con el último), de modo que en sucesivas veces cuando sea cambiado por el bloque en otra posición, irá generando una mayor cantidad de permutaciones aunque varíen poco de una a otra en el tiempo. Esto puede ir especificado con otro parámetro o quedar fijo en la variación del algoritmo. El pseudocódigo sería el siguiente y se colocaría justos donde aparece esta línea:
Fíjese en las siguientes salidas como es barajado siempre el bloque que se intercambió a la última posición y como desde entonces ese bloque se traslada así (con ese nuevo orden entre sus elementos) a la siguiente entrada (sin cambios tras la salida). Para estudiar el caso, aquí la salida de una serie es la entrada de la siguiente, caso que se supone que no será cierto una vez se traslade a una aplicación real (que tras un barajado habrá un juego tal que acaben sus elementos en otro orden). Se marca en azul el bloque que será el último en la siguiente etapa, y se observa de rojo ese bloque en la siguiente fase, posicionado el último y ya barajado. Ese bloque así barajado mantiene su nuevo orden (interno) en lo sucesivo.
Como se puede apreciar, esta variación también permite generar permutaciones aptas para cuando se desea generar jugadas interesantes y entretenidas en juegos que lo necesitan, y en cambio no es aceptable en juegos con apuestas.
Como ya se ha dicho en el encabezado del artículo, es el algoritmo que se usa típicamente para barajar en los juegos de azar (o alguna de sus variantes).
Se usa también en los modelos estadísticos cuando se requiere simular un origen de datos aleatorio. Un caso práctico, para probar la eficiencia de los algoritmos de ordenamiento. hacer simulaciones del clima, etc...
También se usa en sistemas y programas donde se desea usar una sola vez cada elemento de la serie pero de una forma aleatoria, sin recurrir a una estructura adicional de almacenamiento. Se provee un ejemplo al detalle, sobre las listas de reproducción de canciones.
El presente algoritmo, resuelve también este caso, sin la necesidad de recurrir a una segunda estructura donde mover los elementos retirados de la primera.
Imaginemos el caso más corriente, una lista de canciones de la que se desea reproducir cada canción una sola vez, pero que lo hagan en orden aleatorio. Inicialmente se tendrá una lista con las rutas de las canciones, lista que conviene dejar intacta (no intercambiar sus elementos). Se usa un array cuyo contenido (inicialmente) son los índices de las canciones en la lista. Si el orden es aleatorio, se manda barajar el array, si el orden solicitado es el original, se reasigna a cada índice el valor del índice de la lista (el orden natural correlativo). La reproducción finalmente usará como índice, el valor de dicho array. En vez de invocar: Reproducir(Ruta(k)), se invocará: Reproducir(Ruta(Array(k))), así la lista original, no necesita ser tocada ni duplicada para mantener el orden original (es más rápido en memoria asignar valores numéricos, que textos).
Se irán exponiendo ejemplos paso a paso de las implementaciones más relevantes, sobre una serie de 7 elementos, en tablas con columnas, cuyo significado son:
Para el algoritmo descrito en el pseudocódigo (Durstenfeld). Nótese las siguientes cuestiones para este ejemplo:
Para el algoritmo descrito en el pseudocódigo como variante de la implementación de Durstenfeld, posicionando los elementos a la derecha del previo, tal como describieron Fisher-Yates. Nótese las siguientes cuestiones para este ejemplo:
Para la descripción del algoritmo original, empleando para ello, lápiz y papel, es decir tachando de la lista en una línea y escribiendo los resultados en una nueva línea, que será la lista resultante. Esto supone simular 2 estructuras, una que contiene la lista original de la que se extraen y otra donde se insertan. Nótese las siguientes cuestiones para este ejemplo:
Para la descripción del algoritmo Sattolo, variante de Durstenfeld. Nótese las siguientes cuestiones para este ejemplo:
En la siguiente tabla se muestran los resultados de una serie de llamadas a la función, para apreciar como en efecto, no se repiten (observar verticalmente la columna resultados, nunca un elemento en la misma posición en la siguiente llamada).
Escribe un comentario o lo que quieras sobre Algoritmo Fisher-Yates (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)