¿Cómo aleatorizar el orden de aproximadamente 20 elementos con la menor complejidad? (generación de permutaciones aleatorias)Algoritmo para generar orden aleatorio de elementos
Respuesta
Knuth's shuffle algorithm es una buena opción.
Decepcionante que alguien haya dicho algo más, francamente. –
Bueno, estoy decepcionado de que esa es la respuesta. Ya que primero tiene que iterar a través de la lista para llenarlo y luego mezclarlo (con un buen algoritmo), hubiera pensado que había una solución mejor. – SourceOverflow
Hace algunos meses publiqué sobre la obtención de una permutación aleatoria de una lista de enteros. Puede usar eso como una permutación de índices del conjunto que contiene sus elementos, y luego tiene lo que desea.
En el primer post exploro algunas posibilidades, y finalmente obtener la "una función para permutan al azar una lista genérica con O complejidad (n)" , encapsulado adecuadamente para trabajar con datos inmutables (es decir, no tiene efectos secundarios).
En la segunda publicación, la hago distribuida uniformemente.
El código está en F #, ¡espero que no te importe!
Buena suerte.
EDIT: que no tienen una prueba formal, pero la intuición me dice que la complejidad de un algoritmo de este tipo no puede ser inferior a O (n). ¡Realmente apreciaría haberlo hecho más rápido!
recursividad en el segundo artículo es simple ... creo que podría úselo .. – Ante
Todas las permutaciones deben ser posibles, y reorganizar una matriz en una alteración (es decir, una permutación 'p' para la cual' p (k)! = k' para toda 'k') requiere que cada elemento ser visitado. De ahí O (n) el peor caso. ¿O aún no es lo suficientemente formal? –
También O (n) caso promedio por la misma prueba, pensándolo bien, dado que IIRC la proporción de permutaciones de (1 ... n) que son trastornos se acerca a 1/e cuando n se acerca al infinito. –
Una manera simple de aleatorizar el orden es hacer una nueva lista del tamaño correcto (20 en su caso), iterar sobre la primera lista y agregar cada elemento en una posición aleatoria a la segunda lista. Si la posición aleatoria ya está llena, colóquela en la siguiente posición libre.
creo que este pseudocódigo es correcta:
list newList
foreach (element in firstList)
int position = Random.Int(0, firstList.Length - 1)
while (newList[position] != null)
position = (position + 1) % firstList.Length
newList[position] = element
EDIT: Así que resulta que esta respuesta no es realmente tan buena. No es particularmente rápido, ni particularmente aleatorio. Gracias por tus comentarios. Para obtener una buena respuesta, vuelva a la parte superior de la página :-)
En el peor de los casos, este algoritmo es O (n^2) (es decir, si su generador de números aleatorios dice "1, 1, 1, 1, 1, 1, ...", le permití calcular el resto) no muy optimizado –
Poner elementos en la siguiente posición libre lo hace menos aleatorio. Los elementos mantendrán su orden original más que en una mezcla aleatoria. Para solucionarlo, debes elegir una nueva posición aleatoria cuando se toma una posición, lo que por supuesto hace que sea mucho más lenta. – Guffa
Ese es un buen punto Guffa. Nunca me había dado cuenta de eso. Gracias. Al menos he aprendido algo aquí :-) –
Probablemente alguien ya haya implementado el cambio de página por usted. Por ejemplo, en Python puede usar random.shuffle
, en C++ random_shuffle
, y en PHP shuffle
.
hmm ... ¿php tal vez? – Ante
Sorprendentemente, en PHP se llama 'shuffle' :) Actualizaré mi respuesta. –
- 1. Algoritmo para generar un número aleatorio
- 2. Algoritmo para generar polígono 2D aleatorio
- 3. algoritmo para generar diferentes órdenes
- 4. Usando matriz para generar texto aleatorio
- 5. usando rand para generar un número aleatorio
- 6. MapReduce método de orden aleatorio
- 7. Orden aleatorio de filas Matlab
- 8. Algoritmo óptimo para generar un número aleatorio R no en un conjunto de números N
- 9. C# algoritmo para generar jerarquía
- 10. Algoritmo para generar colores únicos
- 11. Algoritmo para generar imágenes simétricas
- 12. linq: ordenar por orden aleatorio
- 13. algoritmo para un espacio aleatorio bordeado por elementos de igual longitud
- 14. Devuelve filas en orden aleatorio
- 15. matriz multidimensional en orden aleatorio
- 16. Esquema XSD que permite el orden aleatorio
- 17. Java Generar número aleatorio {-1,0,1}
- 18. Algoritmo para generar la máscara de bits
- 19. orden aleatorio de imágenes en php
- 20. php orden aleatorio de un foreach
- 21. Métodos de llamada en orden aleatorio (C#)
- 22. Generar un número aleatorio de N-dígitos
- 23. Algoritmo para determinar posibles grupos de elementos
- 24. Reorganizar NSArray/MSMutableArray en orden aleatorio
- 25. ¿Cómo hacer un orden controlado "aleatorio"?
- 26. generar un número aleatorio corto en java?
- 27. Bibliotecas o herramientas para generar texto aleatorio pero realista
- 28. ¿Puede Python establecer la ausencia de orden ser considerado orden aleatorio?
- 29. ¿Cómo generar un número aleatorio en Bash?
- 30. ¿Generar un número aleatorio dentro del rango?
¿Qué quieres decir con cca? –
análisis de correlación canónica? –
¿Qué quieres decir con ca. : P –