No estoy impresionado con la solución devansh. Puedo pensar en Fisher – Yates shuffle – Wikipedia.
Barajar un conjunto dado
El algoritmo de barajado de Fisher-Yates funciona en O (n) complejidad de tiempo. La suposición aquí es que se nos da un
- ¿Cuáles son todos los diferentes tipos de recursividad en la programación?
- ¿Hay alguna canción popular creada usando algoritmos / IA?
- ¿Debo aprender algoritmos si quiero ser desarrollador web / móvil?
- ¿Cuándo deberíamos considerar el uso de algoritmos recursivos al escribir un programa? Discuta en términos de ventajas y desventajas.
- ¿Cuáles son algunos consejos para crear mi propia biblioteca para competencias de codificación?
función rand () que genera un número aleatorio en O (1) tiempo.
La idea es comenzar desde el último elemento, intercambiarlo con un elemento seleccionado al azar del conjunto
matriz (incluido el último). Ahora considere la matriz de 0 a n-2 (tamaño reducido en 1) y repita el proceso
hasta que lleguemos al primer elemento.
+ ———————- +
Verifique que el algoritmo de mezcla de Knuth sea lo más imparcial posible
Cómo probar si una baraja de cartas se ha barajado lo suficiente en Java
Shuffle Fisher-Yates – Wikipedia
Arrastramiento
Barajar una matriz determinada – GeeksforGeeks
https://techblog.bitzino.com/201…
Shuffle Fisher-Yates (Knuth shuffle)
Para barajar una matriz a de n elementos (índices 0..n-1):
para i de n - 1 abajo a 1 do j ← entero aleatorio tal que 0 ≤ j ≤ i intercambiar una [j] y una [i]
El shuffle de Fisher-Yates es imparcial, por lo que cada permutación es igualmente probable. La versión moderna del algoritmo también es bastante eficiente, ya que solo requiere un tiempo proporcional al número de elementos que se barajan y no hay espacio de almacenamiento adicional. La barajadura de Fisher-Yates es similar a sacar al azar boletos numerados (combinatoria: objetos distinguibles) de un sombrero sin reemplazo hasta que no quede ninguno.
Ventajas:
(1) el tiempo asintótico y la complejidad espacial son óptimos. O (N) tiempo y O (1) espacio
(2) garantizado para producir resultados imparciales
(3) puede detenerse a la mitad, o incluso detenerse y reiniciarse repetidamente, generando la permutación de forma incremental según sea necesario
(4) es secuencial no paralelo
===============
Otros algoritmos para barajar:
asigna un número aleatorio a cada elemento del conjunto que se barajará y luego ordena (puede usar la clasificación de Radix) el conjunto de acuerdo con los números asignados
(1) aunque la clasificación general es O (n log n), los números se clasifican de manera eficiente utilizando la clasificación Radix en el tiempo O (n)
(2) produce resultados imparciales
(3) tiene una implementación paralela simple
Pero,
(1) debe asegurarse de que los números aleatorios asignados nunca se dupliquen
(2) requiere un espacio asintóticamente mayor: O (n) espacio de almacenamiento adicional para los números aleatorios
===============
fusionar dos secuencias al elegir repetidamente una de ellas con la misma probabilidad (hasta que la elección se ve forzada por el agotamiento de una secuencia) no produce resultados con una distribución uniforme; en cambio, la probabilidad de elegir una secuencia debe ser proporcional al número de elementos que quedan en ella. De hecho, ningún método que utilice solo eventos aleatorios bidireccionales con igual probabilidad (“lanzamiento de monedas”), repetido un número limitado de veces, puede producir permutaciones de una secuencia (de más de dos elementos) con una distribución uniforme, porque cada ejecución la ruta tendrá como probabilidad un número racional con como denominador una potencia de 2, ¡mientras que la probabilidad requerida es 1 / n! para cada permutación posible no es de esa forma.
===============
¿Cómo verificar que un algoritmo aleatorio sea imparcial?
- tomar un tamaño de matriz relativamente pequeño, realizar una gran cantidad de barajaduras en él,
- cuente cuántas veces observa cada permutación y luego
- realice la prueba de Chi-cuadrado de Pearson para determinar si los resultados están distribuidos uniformemente en el espacio de permutación.
// imagina una baraja de cartas. El superior está numerado N-1. El de abajo es
// numerado 1. Seleccionamos al azar una carta del mazo (incluida la parte superior),
// luego intercambia con el superior, luego, quita el superior.
shuffle nulo (vector & a) {
int N = a.size ();
para (int i = N-1; i> 0; --i) {// esencia, nota, i> 0 no i> = 0
int r = rand ()% (i + 1); // esencia, nota, i + 1 no i. "rand ()% (i + 1)" significa
// genera números de rand de 0 a i
swap (a [i], a [r]);
}
}
// la implementación en C ++ STL
plantilla
void random_shuffle (RandomAccessIterator primero, RandomAccessIterator último,
RandomNumberGenerator y gen)
{
iterator_traits :: diferencia_tipo i, n;
n = (último-primero);
para (i = n-1; i> 0; --i) {
swap (primero [i], primero [gen (i + 1)]);
}
}
