Algoritmo para generar orden aleatorio de elementos

¿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

Fuente

2009-11-07 Ante

¿Qué quieres decir con cca? –

análisis de correlación canónica? –

¿Qué quieres decir con ca. : P –

Knuth's shuffle algorithm es una buena opción.

Fuente

2009-11-07 02:33:48

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!

Fuente

2009-11-07 01:51:47

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 :-)

Fuente

2009-11-07 02:15:23

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.

Fuente

2009-11-07 02:32:47

hmm ... ¿php tal vez? – Ante

Sorprendentemente, en PHP se llama 'shuffle' :) Actualizaré mi respuesta. –

Algoritmo para generar orden aleatorio de elementos

Respuesta

Cuestiones relacionadas