Algoritmo de Fisher-Yates

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.

Historia

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.^[1]​ 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^[2]​ y Durstenfeld en CACM-7^[3]​(1964), a quienes Knuth cita en su libro The Art of Computer Programming^[4]​ 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).

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), 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:

1. Se elige uno al azar.
2. Se escribe en otra línea (a la derecha de los que ya haya escritos).
3. 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 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.

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 Siguiente 

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:

 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) Siguiente 

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:

 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. 

 --- Series Es precalculada, (y de nuevo cada vez que cambiare la cantidad de elementos). Series = Permutaciones(Cantidad) 

 Función: BarajarAleatorio veces = veces + 1 si veces = x entonces <--- 'x' es un valor que se estalece en función de la cantidad de elementos del array. Barajar(Series) veces = 0 Fin si az = Random(entre 0 y Cantidad-1) Array = Series(az) Devolver Array Fin función 

• 6 Otra interesante variación es el algoritmo de Sattolo. Merece ser descrito más ampliamente, en la siguiente sección.

Variante Sattolo

Fue publicado en 1986 en IPL-22,^[5]​ por Sattolo en Information Processing Letters^[6]​ y tiene algunas particularidades que se describen:

• Hace el barajado, con la garantía de que cada elemento no ocupe la posición (a la salida) que ocupaba inicialmente (a la entrada). Para ello se recurre a condicionar la búsqueda aleatoria del elemento al rango de un elemento por debajo de la posición actual, del que se va a reemplazar. Esta es la particularidad interesante de este algoritmo, pero no la única.
• Las permutaciones que realiza una y otra vez, acaban siendo cíclicas (se repiten), aunque no sigan un orden específico, si pueden presentarse secuencias ya aparecidas.
• Hay permutaciones que jamás pueden ocurrir, en series impares (en dichas series solo alcanza a la mitad de las permutaciones, si la serie entra ordenada y se ejecutan el número suficiente de veces). Por ello no es un algoritmo imparcial y debe evitarse su uso en juegos de apuestas (habría la mitad de combinaciones sin ninguna posibilidad real y la otra mitad de combinaciones con el doble de posibilidades), salvo que se tomen las debidas precauciones y sea estrictamente necesario que ningún elemento repita su posición a la salida respecto de la entrada, y siempre que se tenga un conocimiento expreso y exahustivo de los resultados que puede ofrecer. El modo de prevenir dicho problema es garantizar que siempre se usan listas de cantidad pares, añadiendo cuando sean impares un último elemento (que se deseche en uso).
• Éste, es otro caso de algoritmo, que por error se puede llegar a implementar al tratar de implementar el de Durstenfeld, ya que la diferencia entra ambas implementaciones es mínima.

 Recorrer con k desde Cantidad-1 hasta 1 Regresivamente az = Random(entre 0 y k-1) <--- EL CAMBIO: k-1, en vez de k (es la diferencia con Durstenfeld)  tmp = Array(az) Array(az) = Array(k) Array(k) = tmp Siguiente 

• Ya que el algoritmo para conjuntos cuya cantidad de elementos es impar evita la mitad de combinaciones, puede interesar reproducir en algún momento otras permutaciones. El modo de lograr otras combinaciones (entre el resto de combinaciones), consiste en solicitar, un nuevo barajado para todo el conjunto menos 1 (ó varios) elemento (por ejemplo el último o el primero), el cual mantiene su posición. Es decir, hay que generar una combinación nueva que mantenega al menos 1 elemento en la misma posición que antes. Para ello habría que generar el código dedicado al algoritmo (haciéndole creer que tiene un elemento menos, tal como se expresaba en una de las variantes previas). Se consigue así generar diversas series cíclicas (pero no se garantiza que sean todo el resto), dependiendo de cual o cuales sean los valores que se omitan en el barajado, el ciclo de la serie será más largo o más corto. El siguiente pseudocodigo se encarga precisamente de eso.

 Cantidad = Tamaño(Array) Si se pide OmitirUno entonces Cantidad = Cantidad - 1 Fin si Recorrer con k desde Cantidad-1 hasta 1 Regresivamente az = Random(entre 0 y k-1)  tmp = Array(az) Array(az) = Array(k) Array(k) = tmp Siguiente Que se invocaría con la siguiente llamada: Llamada a la función BarajarAleatorio(Array, Sattolo, OmitirUno) 

Variaciones parametrizadas

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.

• Una variación aplicable a todas las implementaciones, consiste en hacer un barajado dejando 1 elemento de ellos (o varios, seguidos) sin barajar, es decir quedando en la misma posición. El modo más sencillo de llevarlo a efecto es mentir al algoritmo en cuestión haciéndole creer que tiene un elemento menos, así baraja todos (los que el algoritmo en cuestión baraje) menos uno (o esos varios). Tal circunstancia puede reclamarse en un parámetro opcional en la llamada a la función. He aquí el pseudocódigo que se podría añadir a cualquiera de ellos, detrás se pone la implementación de Durstenfeld, para apreciar lo que implica (más arriba en Sattolo, se detalla un caso, que hace uso de esta variación, para generar series cíclicas pero diferente a la previa).

 Cantidad = Tamaño(Array) Si se pide OmitirUno entonces <--- OmitirUno sería aquí un parámetro opcional de tipo buleano Cantidad = Cantidad - 1 Fin si 

 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 Siguiente 

 La invocación a una función que implementa esta variación en el algoritmo sería: Llamada a la función BarajarAleatorio(Array, Durstenfeld, OmitirUno) 

• Tal y como se comentaba en la variante numerada como 4 (más arriba), a menudo hay juegos donde es regla del mismo (establecida así en las reglas o acordado entre los propios jugadores) que el barajado no sea excesivo (suelen ser juegos de entretenimiento y no tanto de apuestas por el posible riesgo que entraña), para permitir un juego más interesante y entretenido (por ejemplo un juego como el tute 'cabrón' acepta muy bien esta situación). Puede entenderse como al tiempo que los jugadores con peores cartas o fichas, finalizan antes su juego, sus cartas quedan acumuladas juntas, al tiempo quedan en la partida los jugadores con más triunfos, que al final de la partida quedan también amontonadas sus cartas, con lo que en la baraja, quedan reunidos los triunfos por un lado y las cartas sin valor por otro, de modo que al barajar escasamente los triunfos puedan aún estar algo acumulados y que el reparto de cartas en una nueva partida, provea cartas significativas a un jugador u otro. A veces para garantizar que esto mismo no se enturbia, se procede a repartir varias cartas seguidas a cada jugador, en vez de repartir a cada jugador una carta cada vez. Ambas cosas favorecen que una partida produzca jugadas más interesantes (el algoritmo de dicha variante se halla más arriba como variante 4). Podemos pedir a un algoritmo que cada x elementos del recorrido, omita y barajados (es el pseudocódigo que se presenta a continuación). En este sentido, puede proveerse una variación a los algoritmos proporcionados para favorecer ese escaso barajado, en esta ocasión, tomamos la variante que mejor conjunta con esta causa:

 Entrada: Un Array(0,1,2,3,4... Cantidad-1) de valores. Grupo: un entero que señala cada cuantos se evita un barajado. Salto: un entero que indica cuantos seguidos quedan sin barajar. Cantidad = Tamaño(Array) Fin = (Cantidad \ 2) - 1 Recorrer con k desde 0 hasta Fin <--- Solo recorre la mitad. Si k es congruente con Grupo entonces ---> congruente con, refiere a la operación módulo  (que se traduce como: si ((k mod grupo) = 0) luego k = k + salto En otro caso  az1 = Random(entre 0 y Cantidad-1) az2 = Random(entre 0 y Cantidad-1) tmp = Array(az1) Array(az1) = Array(az2) <---- 'k' no se refiere nunca a la posición de un elemento en el array de esta variante. Array(az2) = tmp Fin si Siguiente 

 La invocación a una función que implementa esta variación en el algoritmo sería: Llamada a la función BarajarAleatorio(Array, Semibarajado, Grupo=13, Salto=3) 

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.

• Todas las implementaciones, puede ser también fácilmente modificadas para hacer el barajado, solo con un subconjunto del rango del array (no a todos), señalando un parámetro de inicio del elemento que se empieza a barajar y otro de la cantidad de elementos afectados. Esto (también) puede aplicarse a listas extremadamente largas donde la ocupación de la memoria pueda ser crítica, o el tiempo necesario para disponer, de todo el array barajado, no es aceptable. Dicha modificación puede solucionar el problema. Es imaginable un array de mil millones de elementos, donde solo se modifica 1 millón de elementos consecutivos cada vez, e incluso una modificación donde se modifica 1 millón de elementos a una distancia de 1000 elementos entre uno y otro(el 1, el 1001, 2001, 3001, 4001.... 1001001), cada vez...

• Todavía todas las implementaciones, admiten aún otra parametrización para hacer un barajado por bloques (lo que comúnmente en los juegos de cartas se llama cortar), que intercambia bloques de cartas y donde los elementos individuales en cada bloque mantiene su posición. En las cartas, al ser barajadas a mano, cada bloque tiene un tamaño indeterminado e independiente del otro. Hay dos formas típicas de cortar: Cortar en 2 montones (de diferente tamaño) con las manos, uno se pone encima del que antes estaba arriba y se repite el proceso varias veces. Otras veces, sobre el tapete se reparten pequeños montones (de cantidades desiguales por lo general, ya que se hace a mano) y se recogen de la mesa en orden diferente al que se ha repartido. Básicamente este es el pseudocódigo que se expone a continuación con la salvedad de que se especifica un tamaño de bloque que se ajusta para todos excepto (quizás) el último montón. La función recibiría un parámetro señalando el tamaño del bloque a considerar.

 Función BarajadoAleatorio Método BarajadoEnBloques Cantidad = Tamaño(Array) Grupos = Cantidad \ Bloque <--- es una división entera, desprecia decimales. Si (Cantidad módulo Bloque) es mayor que 0 entonces sumar 1 a Grupos En la posibilidad de que el último grupo no esté completo se intercambia aparte. Es decir intercambiamos primero el último bloque por el que bloque elegido al azar. Az = Random(entre 0 y Grupos-1) Si Az es distinto de' Grupos-1 entonces <--- si el grupo al azar es el último,      no hace falta intercambiarlo. p = Az * Bloque Recorrer con k desde (Grupos-1)*bloque hasta Cantidad-1 tmp = Array(p) Array(p) = Array(k) Array(k) = tmp p = p + 1 Siguiente Fin si ----> aquí va el inserto que se señala unos párrafos más abajo <--- Grupos = Grupos - 1 Recorrer con J desde (Grupos - 1) hasta 1 Regresivamente Az = Random(entre 0 y J) Si Az es distinto de' J entonces <--- si el grupo al azar es el mismo del     bucle, no hace falta intercambiarlo. p = Az * Bloque n = Az * Bloque Recorrer con k desde n hasta n + Bloque - 1 tmp = Array(p) Array(p) = Array(k) Array(k) = tmp p = p + 1 Siguiente Fin si Siguiente 

 Y la invocación a la función sería así: Llamada a la función BarajarAleatorio(Array, BarajadoEnBloques, Bloque=4) 

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):

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 24 25 26 27 20 21 22 23 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 16 17 18 19 00 01 02 03 20 21 22 23 24 25 26 27 04 05 06 07 08 09 10 11 12 13 14 15 00 01 02 03 24 25 26 27 12 13 14 15 16 17 18 19 04 05 06 07 08 09 10 11 20 21 22 23 04 05 06 07 16 17 18 19 20 21 22 23 24 25 26 27 12 13 14 15 00 01 02 03 08 09 10 11 

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:

 ----> aquí va el inserto que se señala unos párrafos más abajo <--- 

 ' Barajar los elementos internos del que ahora es el último bloque. Min = ((Grupos - 1) * Bloque) Recorrer con k desde Cantidad - 1 hasta Min Regresivamente <---- el barajado es método Durstenfeld,      en este ejemplo, pero podría ser otro Az = Random(entre Min y k) <---- Min: limita el rango inferior en vez de 0 tmp = Array(k) Array(k) = Array(Az) Array(Az) = tmp Siguiente 

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.

 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 <---entrada 04 05 06 07 20 21 22 23 08 09 10 11 24 25 26 27 12 13 14 15 00 01 02 03 19 16 17 18 19 16 17 18 04 05 06 07 24 25 26 27 08 09 10 11 20 21 22 23 00 01 02 03 14 15 13 12 04 05 06 07 24 25 26 27 20 21 22 23 19 16 17 18 14 15 13 12 08 09 10 11 02 01 00 03 02 01 00 03 14 15 13 12 08 09 10 11 20 21 22 23 19 17 16 18 07 04 07 05 26 25 24 27 14 15 12 13 02 08 09 10 11 01 00 03 19 17 16 18 07 04 07 05 20 21 22 23 25 27 24 26 <--- el último     bloque se intercambia consigo mismo esta vez. 

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.

Usos

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.

Reproducción aleatoria de los elementos de una lista

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).

 Si la lista se desea reproducir en la forma original, Necesitamos recrear el orden original: Recorrer con k desde 0 hasta Cantidad-1 Array(k) = k Siguiente Llamada a la función ReproducirLista 

 Si la lista se desea reproducir en forma aleatoria, Desordenamos el array con el algoritmo: Llamada a la función BarajarAleatorio(Array) Llamada a la función ReproducirLista 

 Y la función ReproducirLista sería esta. Recorrer con k desde 0 hasta Cantidad-1 Reproducir(Ruta(Array(k))) Siguiente 

Ejemplos paso a paso con comentarios

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:

• Ciclo: identifica a la variable que controla el bucle, cuando es descendente irá de 6 a 0 cuando sea creciente irá de 0 a 6. Su valor se colorea de rojo
• Rango: Rango de posiciones elegible en cada instante.
• Azar: La posición que ha salido al azar. Su valor se colorea de azul
• Antes: El orden que mantiene la serie antes de aplicar la operación actual.
• Después: El orden que mantiene la serie tras aplicar la operación.
• Resultado: Alguna tabla muestra una columna adicional, para más claridad. Su valor se colorea de rojo.
• Otros detalles:
  • En la tabla que corresponda, se separa la serie con :, para mayor claridad.
  • Aquellos campos que no precisen ser rellenados se señalan con -.
  • Las tablas se completan visualmente, hasta su término (aun cuando no necesite un ciclo final), para acabar de verlo claro.
  • Cuando ambas posiciones (columnas ciclo y azar) se refieran a la misma, el valor se colorea de púrpura.
  • El contenido del campo Después de un ciclo, es el campo Antes del siguiente ciclo, que se repite para mejor seguimiento.

Tabla paso a paso (implementación Durstenfeld)

Para el algoritmo descrito en el pseudocódigo (Durstenfeld). Nótese las siguientes cuestiones para este ejemplo:

• Los intercambios son entre valores de las posiciones ciclo y azar.
• Nótese especialmente como los valores van colocándose a la derecha del separador : que se ha puesto para mejor visibilidad.
• Hay que fijarse también, que aunque han salido 3 veces al azar la posición 0, ello no tiene influencia significativa en el resultado, ya que se refiere a una posición y cada vez será intercambiado por un valor en una posición distinta.
• El ciclo 2, tanto la posición de ciclo, como la de azar refieren a la posición 2, luego el valor se intercambia con sí mismo.
• En esta implementación, no es preciso hacer el ciclo 0 (no hay necesidad de barajar si solo hay 1 elemento entre los que escoger), por tanto se queda el valor que yace en ese momento en dicha posición y se ahorra un ciclo en el bucle.

Ciclo	Rango	Azar	Antes	Después
			0 1 2 3 4 5 6 :	0 1 2 3 4 5 6 :
6	0-6	4	0 1 2 3 4 5 6 :	0 1 2 3 6 5 :4
5	0-5	0	0 1 2 3 6 5 : 4	5 1 2 3 6 : 0 4
4	0-4	0	5 1 2 3 6 : 0 4	6 1 2 3 : 5 0 4
3	0-3	2	6 1 2 3 : 5 0 4	6 1 3 : 2 5 0 4
2	0-2	2	6 1 3 : 2 5 0 4	6 1 : 3 2 5 0 4
1	0-1	0	6 1 : 3 2 5 0 4	1 : 6 3 2 5 0 4
-	0-0	-	1 : 6 3 2 5 0 4	1 6 3 2 5 0 4 :

Tabla paso a paso (implementación Fisher-Yates)

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:

• Las posiciones al azar, no pueden ser iguales que en el ejemplo previo, ya que a medida que aumenten los ciclos, no pueden salir los valores de ciclos ya pasados.
• El intercambio siempre se hará entre el valor de la posicioón elegida al azar y el primero de la serie que entra en juego. Se ha puesto como separador :, para apreciar donde empieza los que entran en juego.
• El resultado va quedando a la derecha de la serie (ver en el encabezado los : a la derecha de la serie en juego.

Ciclo	Rango	Azar	Antes	Después
			: 0 1 2 3 4 5 6	: 0 1 2 3 4 5 6
0	0-6	5	: 0 1 2 3 4 5 6	5 : 1 2 3 4 0 6
1	1-6	3	5 : 1 2 3 4 0 6	5 3 : 2 1 4 0 6
2	2-6	6	5 3 : 2 1 4 0 6	5 3 6 : 1 4 0 2
3	3-6	4	5 3 6 : 1 4 0 2	5 3 6 4 : 1 0 2
4	4-6	5	5 3 6 4 : 1 0 2	5 3 6 4 0 : 1 2
5	5-6	6	5 3 6 4 0 : 1 2	5 3 6 4 0 2 : 1
-	6-6	-	5 3 6 4 0 2 : 1	5 3 6 4 0 2 1 :

Tabla paso a paso (implementación Fisher-Yates original)

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:

• Se emplean los mismos valores de resultado que para el ejemplo anterior, lo que fuerza a elegir otros valores de azar, para que coincidan ambos resultados.
• Aparte de diferenciarse en la representación respecto del anterior y en los valores de la columna Azar, también cambian los valores de la columna rango, pues se sigue el esquema de sacar del sombrero, por lo que en cada ciclo, contiene uno menos entre los que elegir.
• Fijarse en como el valor en la posición libre que señala azar, se tacha en la lista después y pasa al resultado.
• Los ítems tachados, no se cuentan ya al indizar la lista (no existen, en la tabla se dejan, para poder comparar los cambios).

Ciclo	Rango	Azar	Antes	Después	Resultado
			0 1 2 3 4 5 6	0 1 2 3 4 5 6	0 1 2 3 4 5 6
0	0-6	5	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5
1	0-5	3	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3
2	0-4	4	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3 6
3	0-3	3	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3 6 4
4	0-2	0	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3 6 4 0
5	0-1	1	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3 6 4 0 2
6	0-0	-	0 1 2 3 4 5 6	0 1 2 3 4 5 6	5 3 6 4 0 2 1

Tabla paso a paso (implementación Sattolo)

Para la descripción del algoritmo Sattolo, variante de Durstenfeld. Nótese las siguientes cuestiones para este ejemplo:

• No puede emplearse los mismos valores (columna Azar) que en aquella tabla, ya que el rango de posiciones elegible es en cada ciclo uno menor que allí (ver columna rango).
• Nótese la gran diferencia con durstenfeld, la columna rango se ve reducida a un ítem menos entre los que elegir al azar, respecto de la columna ciclo.
• Dado que lo interesante de esta implementación es la capacidad del algoritmo para no repetir valores en la posición inicial, operar con 7 elementos, no sería suficiente para verlo claramente, por ello se amplía la lista a 10 elementos.
• Nótese como el valor de la columna Azar, nunca iguala el valor de la columna Ciclo (ver en pseudocódigo el condicionante del rango en la función Random: Azar = Random(entre 0 y k-1))

Ciclo	Rango	Azar	Antes	Después
			0 1 2 3 4 5 6 7 8 9 :	0 1 2 3 4 5 6 7 8 9 :
9	0-8	6	0 1 2 3 4 5 6 7 8 9 :	0 1 2 3 4 5 9 7 8 : 6
8	0-7	4	0 1 2 3 4 5 9 7 8 : 6	0 1 2 3 8 5 9 7 : 4 6
7	0-6	4	0 1 2 3 8 5 9 7 : 4 6	0 1 2 3 7 5 9 : 8 4 6
6	0-5	1	0 1 2 3 7 5 9 : 8 4 6	0 9 2 3 7 5 : 1 8 4 6
5	0-4	1	0 9 2 3 7 5 : 1 8 4 6	0 5 2 3 7 : 9 1 8 4 6
4	0-3	3	0 5 2 3 7 : 9 1 8 4 6	0 5 2 7 : 3 9 1 8 4 6
3	0-2	0	0 5 2 7 : 3 9 1 8 4 6	7 5 2 : 0 3 9 1 8 4 6
2	0-1	1	7 5 2 : 0 3 9 1 8 4 6	7 2 : 5 0 3 9 1 8 4 6
1	0-0	0	7 2 : 5 0 3 9 1 8 4 6	2 : 7 5 0 3 9 1 8 4 6
-	-	-	2 : 5 0 3 9 1 8 4 6	: 2 7 5 0 3 9 1 8 4 6

Resultados de una serie de llamadas consecutivas

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).

• Para esta tabla se han realizado 12 llamadas y se prescindido de los pasos internos de la función. Y para la ocasión se ponen las columnas siguientes:
  • Llamada: El índice indica la enésima llamada a la función BarajadoAleatorio para la implementación de Sattolo.
  • Azar: Contiene la lista de posiciones aleatorias obtenida (internamente) en esa llamada (por si desea recrearse manualmente siguiendo el esquema de la tabla previa).
  • Entrada y Salida: Son columnas que muestran la lista a la entrada y la salida de la función. La lista de la columna Salida de una llamada a la función, es la misma lista que se consigna en la columna Entrada de la siguiente llamada.
• Nótese como en la columna Azar, verticalmente siempre los valores que salieron son menores, que el número que indica el encabezado (se ha coloreado toda la sub-columna encabezada por el 8 de color rojo, para apreciarse mejor, pero se aplica a todas ellas). La posición horizontal en dicha columna Azar, indica el valor obtenido por la función Random en cada ciclo interno del bucle, dado el rango en el que se ve obligado a elegir).
• Apréciese, como en la columna Salida, ningún valor se repite en la misma posición que tenía en la llamada anterior (se ha coloreado de azul verticalmente, la sub-columna 6ª, para dirigir mejor la vista, pero se aplica a todas ellas)). Una tabla similar con cualquiera de las otra implementaciones arrojaría muchas coincidencias.

Llamada	Azar	Entrada	Salida
	9 8 7 6 5 4 3 2 1	0 1 2 3 4 5 6 7 8 9	0 1 2 3 4 5 6 7 8 9
1	6 4 4 1 1 3 0 1 0	0 1 2 3 4 5 6 7 8 9	2 7 5 0 3 9 1 8 4 6
2	0 3 6 4 1 3 2 0 0	2 7 5 0 3 9 1 8 4 6	9 8 6 5 4 7 3 1 0 2
3	4 6 0 3 2 1 1 1 0	9 8 6 5 4 7 3 1 0 2	7 1 0 2 8 6 5 9 3 4
4	7 6 4 5 4 0 2 1 0	7 1 0 2 8 6 5 9 3 4	2 3 1 0 7 4 6 8 5 9
4	0 7 4 0 2 0 0 1 0	2 3 1 0 7 4 6 8 5 9	4 0 3 5 6 1 9 7 8 2
6	2 3 2 5 4 1 0 0 0	4 0 3 5 6 1 9 7 8 2	9 7 8 4 0 6 1 2 5 3
7	3 3 4 1 3 0 0 1 0	9 7 8 4 0 6 1 2 5 3	8 6 1 2 9 5 7 0 3 4
8	8 2 5 2 1 3 1 1 0	8 6 1 2 9 5 7 0 3 4	7 8 9 0 2 6 4 5 1 3
9	5 5 6 5 0 2 2 0 0	7 8 9 0 2 6 4 5 1 3	8 0 5 2 9 7 1 4 3 6
10	4 3 2 2 1 0 0 1 0	8 0 5 2 9 7 1 4 3 6	1 3 7 6 8 0 4 5 2 9
11	3 3 1 2 1 2 1 0 0	1 3 7 6 8 0 4 5 2 9	2 8 1 0 4 5 7 3 9 6
12	4 3 0 4 2 3 1 1 0	2 8 1 0 4 5 7 3 9 6	5 3 7 8 9 1 6 2 0 4

Test de aleatoriedad sobre las implementaciones

Véase también

• Aleatoriedad
• Entropía (información)
• Número aleatorio
• Pruebas de aleatoriedad
• Secuencia pseudoaleatoria
• Teoría de probabilidad
• Variable aleatoria

Referencias

1. Fisher, Ronald A.; Yates, Frank (1948) [1938]. Statistical tables for biological, agricultural and medical research (3rd edición). Londres: Oliver & Boyd. pp. 26-27. OCLC 14222135.  Nota: la 6ª edición, ISBN 0-02-844720-4, es , pero ofrece un algortmo de barajado algo diferente, por C. R. Rao.
2. Moses, Lincoln E.; Oakford, Robert V. (1963) [1963]. Tables of Random Permutations (1ª edición). Stanford (California): Stanford University Press. pp. ???. ISBN 0-8047-0148-2. 
3. doi 10.1145/364520.364540
4. Knuth, Donald Erwin (1969 (1981 2ªed.)). Seminumerical algorithms. The Art of Computer Programming 2. Reading, MA: Addison–Wesley. pp. 124-125 (139-140 en 2ª ed.). ISBN 0-201-03822-6. 
5. doi 10.1016/0020-0190(86)90073-6
6. Sandra Sattolo (25 de junio de 1985). «An algorithm to generate a random cyclic permutation» [Un algoritmo para generar una permutación cíclica aleatoria]. En Elsevier B.V., ed. Istituto di Matematica, Facolta' di Scienze Matematiche e Fisiche, Universita' degli Studi di Udine, via P. Mantica, 33100 Udine, Italy. Information Processing Letters (30-mayo-1986) 22 (6): 315-317. 

•   Datos: Q6522952