Algoritmo de Fisher-Yates

Y por tanto debería constar en las bibliotecas de ordenamiento como Random Sort al menos.

Posteriormente otros autores (probablemente sin conocimiento previo de dicha publicación) elaboraron el mismo algoritmo.

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.

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

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.

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

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.

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.