alt=Descripción gráfica de la versión de Durstenfeld del algoritmo de mezclar de Fisher-Yates|miniaturadeimagen|Representación gráfica de la versión de Durstenfeld del algoritmo de Fisher-Yates para mezclar un arreglo.
El algoritmo de Fisher-Yates (o alguna variante del mismo) es un método para barajar aleatoriamente una secuencia de elementos, garantizando que cada permutación tenga la misma probabilidad de ocurrir. Funciona recorriendo la lista, generalmente de atrás hacia adelante, y en cada paso intercambia el elemento actual con uno seleccionado aleatoriamente de los elementos no vistos hasta ese momento. Es un algoritmo de ordenamiento ampliamente utilizado para generar mezclas aleatorias de colecciones, como barajas de cartas o listas de reproducción.
Historia El algoritmo Fisher-Yates aparece documentado por primera vez por Ronald A. Fisher y Frank Yates en el libro Statistical tables for biological, agricultural and medical research. Nota: la 6ª edición, ISBN 0-02-844720-4, es disponible a través de la red, pero ofrece un algoritmo de barajado algo diferente, por C. R. Rao. 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 algunos países latinoamericanos, a este algoritmo se lo conoce como el «barajado del sombrero», dado que la descripción que hicieron Fisher y Yates de él, es la que se lleva a cabo habitualmente cuando, –por ejemplo–, se hace una rifa.
Transcripción a la programación 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), mientras que Durstenfeld usa la propia matriz para llevar a cabo todo el algoritmo, necesitando solo como memoria extra una variable temporal.
Descripción del algoritmo La forma más simple de entenderlo es partir de la forma popular: Se escribe cada número en un papelito doblado (construir el array), se introducen todos los números en un sombrero, se agita el contenido dentro del sombrero (se barajan), luego se van sacando papelitos que son dispuestos en el mismo orden en que se sacan, hasta que no quede ninguno. El resultado es la lista barajada. La descripción (grosso modo) que dan Fisher y Yates es la siguiente: Se escribe en una línea los números del orden de la serie de 0 (ó 1) hasta el final de la serie (se supone una serie corta, manejable mediante lápiz y papel) y se dispone debajo otra línea vacía. Y se hace lo siguiente: Se elige uno al azar. Se escribe en otra línea (a la derecha de los que ya haya escritos). Se tacha de la línea anterior (el número salido al azar). 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. La descripción de Durstenfeld varía de la de Fisher y Yates, en que al llevarla a cabo en un programa se trata de ahorrar memoria y por tanto trata de usar el mismo array, para ello, va intercambiando el valor de la posición al azar, y lo remplaza por el último del array no remplazado ya. Es decir al iniciar el algoritmo, el primero elegido se remplaza por el último, en el siguiente ciclo se elige al azar entre todos menos el último, que ahora se remplaza por el penúltimo, y de nuevo se elige otro al azar entre todos menos los dos últimos, etc. Básicamente, Durstenfeld escribe el resultado a la izquierda del previo, en tanto que Fisher-Yates, lo hacía a la derecha.
Es un error común pensar que la aleatoriedad de la lista depende del algoritmo de barajado (siempre que sea correcto, que para cada posición sea elegida una posición al azar), cuando en realidad depende 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.
Pseudocódigo del algoritmo É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). Algoritmo BarajadoAleatorio: Entrada: Un Array(0,1,2,3,4... Cantidad-1) de valores. Salida: El mismo array con sus valores en posiciones aleatorias. Definición de variables: Cantidad: Un entero que señala la cantidad total de ítems que tiene el array. k: Un entero, que rige la cuenta del bucle. az: Un entero, elegido por una función Random en el rango 0-k (nótese que k se va reduciendo). tmp: Un entero, que ha de contener un valor para intercambiar valores entre 2 posiciones. Funciones auxiliares: Tamaño: Una función que devuelve la cantidad de elementos que contiene el array. Random: Una función que devuelve un número aleatorio de un rango de valores.
Cantidad = Tamaño(Array) Recorrer con k desde Cantidad-1 hasta 1 Regresivamente az = Random(entre 0 y k)
tmp = Array(az) Array(az) = Array(k) Array(k) = tmp SiguienteAunque 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: Algoritmo BarajadoAleatorio: Las variables son las mismas del caso anterior, excepto, que en la entrada en vez de un array, se recibe una estructura (por ejemplo una colección, una lista enlazada, un árbol, etc.) Recorrer con k desde Cantidad-1 hasta 1 Regresivamente az = Random(entre 0 y k)
Estruc.AñadirItem(Estruc.Item(az), Al Final) Estruc.BorrarItem(az) SiguienteEs 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 describieron Fisher y Yates. 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: Estruc.AñadirItem(Estruc.Item(az), En Posición k) 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).
Variantes 1 El algoritmo, presenta algunas variantes. De hecho es bastante fácil que al tratar de implementar dicho algoritmo se acabe haciendo este otro. Cuya particularidad más destacable, es que siempre que se baraja se elige de nuevo entre todos los existentes (es como si el sombrero tuviera posiciones donde se coloca cada uno cuando se meten, y tras barajar el elemento sacado del sombrero se volviera a introducir de nuevo y se sacaran tantos como elementos hay en el sombrero y finalmente se expusiera el orden en que los elementos aparecen en el sombrero): Recorrer con k desde 0 hasta Cantidad - 1 az = Random(entre 0 y Cantidad-1)
tmp = Array(az) Array(az) = Array(k) Array(k) = tmp Siguiente 2 También es posible modificar el algoritmo para solucionar una lista cuya cantidad de elementos se desconoce (no tiene una cantidad fija, caso típico de una estructura que permite añadir y eliminar elementos).
3 También es posible modificar el algoritmo, de Durnstenfeld, para que opere en el orden que describe Fisher-Yates (siguiente a la derecha del previo). Es decir, los valores obtenidos se van colocando en la posición más baja y creciendo. Nótese que no hay pérdida de eficiencia, y nótese que el recorrido le basta llegar hasta el penúltimo. Recorrer con k desde 0 hasta Cantidad - 2 az = Random(entre k y Cantidad-1)
tmp = Array(az) Array(az) = Array(k) Array(k) = tmp Siguiente 4 Una variante interesante para determinados juegos, es aquella capaz aun de generar todas las combinaciones posibles, pero que genere algunas con más frecuencia que otras, pero todavía de forma aleatoria, es decir que a pesar de ello no sea predecible. Motivado para permitir un juego que provea jugadas más interesantes y entretenidas con un reparto (de cartas, fichas, etc.) no tan imparcial (en cuanto a lo que sale, no en cuanto a quien sale). (para acentuar esta característica ver la 2ª parte de la sección variaciones parámetrizadas). El siguiente pseudocódigo, obtiene 2 números al azar y ambos señalan posiciones, que son las que se intercambian entre sí. Si sucede que la posición de origen y destino es la misma, el intercambio no produce un cambio real. También puede suceder que una o ambas posiciones, hayan salido antes ya. Ambas cosas permiten que la serie no sea tan diferente entre la entrada y la salida, comparada con las otras implementaciones. Es fácil percibir que al no usarse como índice el contador del bucle, sino 2 índices elegidos al azar, pueda haber posiciones que en un barajado no salga y por tanto aumenta la probabilidad de que más de 1 elemento mantenga a la salida, la misma posición que tenía a la entrada. Puede aumentarse notablemente la eficacia de lo que trata de hacer el algoritmo si el bucle solo recorre la mitad de los elementos (mitad de posibilidades de que salga cada posición). He aquí el pseudocódigo de esta variante: Fin = (Tamaño(Array) \ 2) - 1 Recorrer con k desde 0 hasta Fin <--- Solo recorre la mitad. az1 = Random(entre 0 y Cantidad-1) az2 = Random(entre 0 y Cantidad-1)
tmp = Array(az1) <---- 'k' no se refiere nunca a la posición de un elemento en el Array(az1) = Array(az2) <--- array de esta variante, como sucede en el resto de variantes. Array(az2) = tmp Siguiente 5 Hay aun una forma diferente de concebir el algoritmo de barajado, que ya no se ajusta al artículo, pero que aun resulta de interés presentar aquí. Sea una estructura en la que las permutaciones están ya precalculadas y almacenadas y se usa una función random para elegir (el índice) cual de las permutaciones en la estructura es la que se entrega. Esta variante, sin embargo queda en la práctica limitada a series cuya cantidad de elementos sean relativamente pequeño, dado el espacio de memoria que consume almacenar todas la serie de permutaciones posibles. Aunque cuando la velocidad es fundamental esta solución resulta la más apta. Es ideal que una vez halladas las permutaciones diferentes estas sean barajadas (para que no consten el orden creciente en que posiblemente las devuelva la función) y que se haga lo mismo cada cierto número de entregas. Variables nuevas: Series: Es una estructura acorde para contener arrays donde cada array mantiene una permutación distinta de la serie (un árbol de arrays, otro array de arrays, etc.). Veces: Es un contador, para barajar el orden de los arrays en la estructura series, cada vez que alcanza cierto valor, para favorecer la aleatoriedad. X: Un valor límite que controla el límite de veces. Este valor es dependiente de la cantidad de permutaciones Funciones accesorias Permutaciones: Sería una función de combinatoria, que devuelve una estructura de arrays, con todas las series posibles, donde cada array contiene una serie distinta. Barajar: Es un algoritmo de barajado aleatorio (como los descritos), con la particularidad de que cambiaría los punteros de los índices del array, en vez del contenido.