mezcla aleatoria
Casi todos los programadores han escrito algoritmos similares a "barajar", es decir, barajar aleatoriamente una matriz y generarla. Aunque es muy simple, si lo estudias en profundidad, este pequeño algoritmo también es muy particular. . Cuando entrevisto a programadores, a menudo les pido que escriban una función aleatoria en el momento, a partir de la cual puedo observar su comprensión de este problema y sus habilidades básicas para escribir programas.
Antes de discutir en profundidad, primero se debe definir un concepto básico: ¿Cuál es la esencia del algoritmo de barajado? En otras palabras, ¿qué tipo de resultados aleatorios son "correctos"?
Yunfeng una vez tuvo una publicación de blog que discutía específicamente este tema. También dio una definición más precisa. Después de la función de barajado, si se puede garantizar que la probabilidad de que cada dato aparezca en todas las posiciones sea igual, entonces este algoritmo. cumple con los requisitos. Bajo esta premisa, se puede obtener un buen algoritmo reduciendo la complejidad del tiempo y del espacio tanto como sea posible.
El primer algoritmo de barajado:
Saca una carta al azar y comprueba si se ha sacado antes. Si se ha sacado antes, vuelve a sacarla hasta que encuentre una carta que no lo haya hecho. robadas. Roba la carta, luego ponla en la cola barajada y repite el proceso hasta que se hayan extraído todas las cartas.
Probablemente esté más en línea con el pensamiento intuitivo del cerebro sobre la mezcla. Este algoritmo aparece a menudo en los resultados de las entrevistas que encontré. Aunque cumple con nuestros requisitos básicos para la mezcla de algoritmos, este algoritmo no es bueno. de todo, su complejidad es O(N2), y se necesita espacio de memoria adicional para guardar el índice de la tarjeta que se ha extraído. Por lo tanto, cuando la cantidad de datos es relativamente grande, la eficiencia se reducirá considerablemente.
El segundo algoritmo:
Supongamos que el número de tarjetas es n, primero prepare n números aleatorios que no sean fáciles de colisionar y luego clasifíquelos, puede obtener un orden desordenado. Para obtener la secuencia, baraja las cartas de acuerdo con esta secuencia.
Este también es un algoritmo que cumple con los requisitos, pero también requiere espacio de almacenamiento adicional, y la complejidad también dependerá del algoritmo de clasificación utilizado, por lo que todavía no es un buen algoritmo.
El tercer algoritmo:
Se seleccionan e intercambian dos cartas al azar cada vez, y el intercambio finaliza después de un cierto número de repeticiones
void shuffle(int* datos, longitud int)
{
for(int i=0; ilt; SWAP_COUNTS; i )
{
// Rand(min, max) devuelve un número aleatorio en el intervalo [min, max)
int index1 = Rand(0, length);
int index2 = Rand(0, length) );
p>
std::swap(datos[índice1], datos[índice2]);
}
}
Este es otro método común de barajar. La pregunta más interesante es el "número de intercambios". Cálculo simple: después de intercambiar m veces, la probabilidad de que una carta específica nunca se haya extraído es ((n-2)/n)^m. Si requerimos que esta probabilidad sea menor que 1/1000, entonces mgt; ln (10)/ln(1-2/n), para 52 cartas, este número es aproximadamente 176 veces. Cabe señalar que esta es la probabilidad de que "una carta específica" nunca se haya extraído. satisfecho La probabilidad de que "cualquier carta" no se extraiga es inferior a 1/1000 y el número de veces requeridas es mayor, pero el cálculo de esta probabilidad es más complicado. Los amigos interesados pueden intentarlo.
Actualización: esta probabilidad es, se puede consultar el proceso de cálculo aquí. Según esta probabilidad, se necesitan 280 intercambios para cumplir con los requisitos.
El cuarto algoritmo:
A partir de la primera carta, intercambie cada carta por una carta aleatoria
void shuffle(int* data, int length)
{
por (int i=0; ilt; longitud; i)
{
int index = Rand(0, longitud);
std::swap( datos [i], datos[índice]);
}
}
Obviamente, este algoritmo cumple con nuestros requisitos anteriores y la complejidad del tiempo es O( N), y no se requiere espacio temporal adicional. Parece que hemos encontrado el algoritmo óptimo, pero este no es el caso. Veamos el siguiente algoritmo.
El quinto algoritmo:
void shuffle(int* data, int length)
{
for(int i=1; ilt; longitud; i )
{
int index = Rand(0, i
std::swap(datos[i], datos [ index]);
}
}
Surge una situación interesante. Este algoritmo es muy similar al tercer algoritmo. Intuitivamente, parece que la capacidad de. "desordenado" los datos son más débiles que el tercero, pero de hecho, este algoritmo es más fuerte que el tercero. No es fácil probar esto estrictamente. Requiere algunas habilidades matemáticas. Los amigos que estén interesados pueden consultar este artículo o la publicación del blog de Matrix67. También puede comprender esto simplemente para los datos de n tarjetas. Hay n! situaciones posibles, pero el cuarto algoritmo puede producir n^n permutaciones, que son mucho más grandes que la disposición real, y n^n no puede ser divisible por n!, por lo que la diferencia entre las cartas definidas por el algoritmo cuatro Durante el intercambio Durante el proceso, es muy probable que una tarjeta se intercambie de un lado a otro y luego se devuelva a su posición original, por lo que este algoritmo no es óptimo. Las posibles combinaciones de la salida del Algoritmo 5 son exactamente n!, por lo que este algoritmo es perfecto.
El asunto aún no ha terminado. Si realmente quieres encontrar un algoritmo óptimo, ¡busquemos el campeón final!
El sexto algoritmo:
void shuffle(int* data, int length)
{
std::random_shuffle(data , longitud de datos);
}
Sí, usar la función de biblioteca estándar de C es la mejor solución. De hecho, std::random_shuffle también adopta el cuarto método en la implementación. ser la misma frase, "No reinventes la rueda"
No quiero escribir - -