Estoy escribiendo este contenido de esta publicación de blog que compara dos algoritmos de barajado diferentes para ver cuál es imparcial.
¿Qué es un algoritmo aleatorio aleatorio?
Considere una matriz con elementos distintos A [1… n]
- Cómo encontrar el número máximo de árboles de expansión mínima en un gráfico
- ¿Cuáles son algunos patrones de diseño de C ++ para aplicaciones en tiempo real como el comercio algorítmico?
- ¿Cómo puede 100 determinar el número de comparaciones en 'Búsqueda binaria'?
- Recientemente me enamoré de las estructuras de datos y algoritmos. ¿Qué idioma (s) y qué rama (s) de matemáticas le servirían mejor y qué tipo de trabajos de entrada debería buscar una vez que lo lleve a un nivel decente, unos 4-6 meses después?
- Cómo comenzar a aprender algoritmos de reconocimiento de voz
Un algoritmo aleatorio perfectamente imparcial barajaría aleatoriamente todos los elementos de la matriz de manera que después de barajar:
1.La probabilidad de que la operación de barajado produzca una permutación particular de la matriz original es la misma para todas las permutaciones (es decir, ¡ya que hay n! permutaciones, la probabilidad de que la operación aleatoria produzca una permutación particular es 1 / n!
2.Para cualquier elemento e en la matriz y para cualquier posición j (1 <= j <= n), la probabilidad de que el elemento termine en la posición A [j] es 1 / n
Considere dos algoritmos de barajado
SHUFFLE 1
barajar (A [1… n]) {
para i = 1 a n {
// Encuentra un entero aleatorio entre 1 yn inclusive
int rand = ALEATORIO (1, n);
intercambie A [i] con A [rand];
}
}
SHUFFLE 2
barajar (A [1… n]) {
para i = 1 a n {
// Encuentra un número entero aleatorio entre i y n inclusive
int rand = RANDOM (i, n);
intercambie A [i] con A [rand];
}
}
¿Cómo se comparan estos dos algoritmos de barajado? Simulemos y descubramos.
Simulación de Shuffle 1
A continuación se muestra una simulación de Shuffle 2 con una matriz de.
Conteo de permutaciones:
{1,2,3} – cuenta 4
{1,3,2} – cuenta 5
{2,1,3} – cuenta 5
{2,3,1} – cuenta 5
{3,1,2} – cuenta 4
{3,2,1} – cuenta 4
Conclusión: Shuffle 1 está sesgado
Simulación de Shuffle 2
A continuación se muestra una simulación de Shuffle 2 con una matriz {1,2,3}.
Conteo de permutaciones:
{1,2,3} – cuenta 1
{1,3,2} – cuenta 1
{2,1,3} – cuenta 1
{2,3,1} – cuenta 1
{3,1,2} – cuenta 1
{3,2,1} – cuenta 1
Conclusión: Shuffle 2 es un algoritmo de barajado perfecto imparcial
¿Podemos demostrar que Shuffle 2 producirá un shuffle imparcial en todos los casos?
Para cualquier elemento e, la probabilidad de que se baraje en la primera posición
= probabilidad de que se seleccione para intercambiar cuando i = 1
= 1 / n
Para cualquier elemento e, la probabilidad de que se baraje en la segunda posición
= probabilidad de que NO se seleccione para la primera posición x probabilidad de que se seleccione para intercambiar cuando i = 2
= (n-1) / nx 1 / (n-1)
= 1 / n
…
Para cualquier elemento e, la probabilidad de que se baraje en una posición particular = 1 / n
Espero que esta explicación haya sido útil. Si está interesado, puede practicar resolviendo desafíos de programación o leer preguntas técnicas de entrevistas sobre estructuras de datos y algoritmos en mi blog.
