WhatsApp

  
¿Qué es el algoritmo Fisher-Yates?
Fisher-Yates
¿Qué es el algoritmo Fisher Yates  ?

El algoritmo Fisher-Yates,  recibe su nombre de sus creadores  Ronald A. Fisher Frank Yates es un método para reordenar de manera aleatoria los elementos de una lista. Este algoritmo es comúnmente utilizado para mezclar elementos en un orden aleatorio como música, video o una baraja de cartas,  si bien técnicamente  es un algoritmo de permutaciones y encaja  en la categoría de los algoritmos de ordenamiento, su fin es  el opuesto, desordenar los ítems que contiene. 

Nota:   "No confundir con el método de la baraja o inserción directa ",

                   

Pasos del Algoritmo.
  1. Inicialización: Se comienza con una lista de elementos que se desea reorganizar aleatoriamente. Esto puede ser una lista de números, letras, objetos o cualquier tipo de datos.

  2. Recorrido de la lista desde el final hacia el principio: El algoritmo recorre la lista desde el último elemento hasta el primero.

  3. Selección aleatoria e intercambio: En cada iteración del bucle, se selecciona aleatoriamente un índice entre 0 y el índice actual (inclusive). Este índice aleatorio corresponde a un elemento en la lista. Luego, se intercambia el elemento en el índice actual con el elemento en el índice seleccionado aleatoriamente. Esto garantiza que cada elemento tenga la misma probabilidad de terminar en cualquier posición en la lista final.

  4. Repetición del proceso: Este proceso se repite para cada elemento en la lista, asegurando que cada elemento se coloque aleatoriamente en la lista reorganizada.

  5. Resultado: Una vez que se completa el recorrido de la lista, todos los elementos se habrán reorganizado aleatoriamente en la lista resultante.

Ejemplo de implementación con Python.

A continuación se muestra como seria la implementación en Python de este algoritmo:

import random
def shuffle_list(input_list):
    # Creamos una copia de la lista original
    shuffled_list = input_list[:]
    # Obtenemos la longitud de la lista
    n = len(shuffled_list)
    # Iteramos sobre cada elemento de la lista, comenzando desde el último
    for i in range(n - 1, 0, -1):
        # Seleccionamos un índice aleatorio entre 0 y i (incluyendo i)
        j = random.randint(0, i)
        # Intercambiamos los elementos en las posiciones i y j
        shuffled_list[i], shuffled_list[j] = shuffled_list[j], shuffled_list[i]
    return shuffled_list

Ejemplo de Uso
#Ejemplo de Uso 
original_list = [1, 2, 3, 4, 5]
shuffled_list = shuffle_list(original_list)

#Imprimimos el resultado la lista original vs copia. print("Lista original:", original_list) print("Lista mezclada:", shuffled_list)   
Resultado 

El resultado de dicha operación pude al ser aleatorio siempre arrojara un resultado distinto, a continuación se muestran 3 resultados obtenidos: 

Resultado 1.

 Lista original: [1, 2, 3, 4, 5]    
 Lista mezclada: [5, 2, 1, 4, 3]

Resultado 2. 

Lista original: [1, 2, 3, 4, 5]     
Lista mezclada: [2, 4, 3, 5, 1] 

Resultado 3. 

Lista original: [1, 2, 3, 4, 5]     
Lista mezclada: [5, 1, 3, 2, 4] 

Aplicaciones: 
  1. Juegos de azar y entretenimiento: El algoritmo Fisher-Yates se utiliza en la creación de juegos de azar en línea, como juegos de cartas, dados, ruleta y otros juegos de casino virtuales donde se requiere aleatoriedad en la distribución de cartas o en los resultados.

  2. Generación de contraseñas seguras: Es común utilizar el algoritmo Fisher-Yates para generar contraseñas aleatorias y seguras. Esto garantiza que las contraseñas sean lo más impredecibles posible, ya que cada carácter se selecciona aleatoriamente de un conjunto de caracteres posibles.

  3. Pruebas y experimentos científicos: En la investigación científica y las pruebas experimentales, a menudo es necesario realizar muestreos aleatorios de datos. El algoritmo Fisher-Yates puede utilizarse para aleatorizar los datos de manera que los sesgos y patrones no afecten los resultados del experimento.

  4. Optimización de algoritmos genéticos: Los algoritmos genéticos son técnicas de optimización inspiradas en la evolución biológica. En algunos casos, es necesario realizar una selección aleatoria de genes o individuos. El algoritmo Fisher-Yates puede utilizarse para aleatorizar el proceso de selección.

  5. Mezcla de listas y reproducción de música: Las aplicaciones de reproducción de música y listas de reproducción suelen utilizar el algoritmo Fisher-Yates para mezclar las canciones de manera aleatoria y proporcionar una experiencia de escucha variada y agradable para los usuarios.

  6. Pruebas de rendimiento y estrés: En pruebas de rendimiento de software y sistemas, a veces es necesario simular el comportamiento aleatorio de los usuarios o eventos. El algoritmo Fisher-Yates puede utilizarse para generar secuencias aleatorias de eventos con fines de prueba y análisis de rendimiento.




En resumen, las listas y las tuplas son estructuras de datos importantes en Python, cada una con sus propias características y casos de uso. La elección entre una lista y una tupla dependerá de los requisitos específicos del programa y la naturaleza de los datos que se están manipulando.
Daniel Ixbalanque 1 abril, 2024
Compartir


Iniciar sesión dejar un comentario

  
¿Qué es el algoritmo Bubble Sort (Ordenamiento Burbuja) ?
Bubble Sort (Ordenamiento Burbuja)