Una manera eficaz de aleatorización de un array - Código Aleatorio

Question

I se hizo esta pregunta en una entrevista y me dio varias soluciones, pero el entrevistador no estaba convencido. Estoy interesado en encontrar una solución. Por favor lanzar en sus puntos de vista:

Q: Escribir una estructura de datos eficiente para implementar el shuffle en un iPod. Debe reproducir todas las canciones, cada vez en orden aleatorio diferente, la misma canción no debe repetirse. (En su mayoría O (n))

Una solución, pensé que después de la entrevista: Puedo hacer un estudio aleatorizado rápida tipo sin recursividad. Dónde estamos al azar, elegimos 1 pivote O (1) y luego hacer quicksort O (n). Ahora canciones serán ordenados en un orden y jugar hasta el final. Una vez que llega al final, voy a elegir de nuevo un pivote al azar y, repetir este proceso una y otra vez.

Saludos, Sethu

Answer 1

Coloque todas las canciones de una gran variedad ... Para cada elemento de la matriz que intercambio con una posición aleatoria.

Answer 2

Algoritmo Fisher-Yates . Sea consciente de los errores de implementación mencionados en esa página, como su respuesta actualmente aceptada cae falta de uno.

Answer 3

Bueno, la primera solución en tiempo lineal que viene a la mente:

Se podría hacer una lista enlazada de todas las canciones, que tomaría cerca de O (n) (dado que las inserciones son operaciones de tiempo constante). A continuación, generar un número aleatorio, módulo el tamaño de la lista para obtener un índice de azar, y eliminar dicho índice y añadir a una nueva lista (ambos de los cuales son operaciones de tiempo constantes).

Una inserción para cada O (n) + una eliminación para cada O (n) + un segundo O inserción (n). Esto global conducirá a una solución de tiempo lineal.

Editar : Me olvidé por completo caminar la lista. Así que, en cambio, que podría hacer que el resultado de una matriz de longitud fija. Pop de la cabeza de la lista enlazada, asignarle el índice de azar, y rellenar la matriz.

Answer 4

Nate de (editado) y Brian de algoritmos son el Algoritmo Fisher-Yates O (n), mientras baraja por clasificación es O (nlogn), pero en realidad puede ser más rápido en la práctica (http://en.wikipedia.org/wiki / Fisher% E2% 80% 93Yates_shuffle # Comparison_with_other_shuffling_algorithms). Conseguir mal barajado canción puede tener consecuencias insignificantes, pero si usted está escribiendo un algoritmo de barajar para un juego de póquer en línea, asegúrese de que sabe lo que está haciendo (http://www.cigital.com/news/index.php?pg= art & artid = 20).

Answer 5

Soy un principiante, permítanme decir una solución que los ataques a la mente, si algo está mal por favor me dan a conocer.

Vamos a suponer canciones se almacenan en la lista, ya sea vinculado forma simple o doble. Cada vez que se abre el reproductor de música elegir un número aleatorio menor que (cualquier número que desea) asumir k, e invertir cada k nodos en la lista, de manera similar hacerlo dos veces o al tres veces como máximo (como desee) que tomaría O ( 2n) o o (3n) para mezclar. finalmente tendrá un puntero al último nodo de la lista. Y cada vez que se escucha una canción (un nodo es visitado) eliminar el nodo e insertarlo al lado del último nodo que se puede hacer en O (1) tiempo. Esto continúa hasta que el reproductor de música está cerrado.

Gracias, Deseosos de conocer la exactitud de la respuesta.

Answer 6

Lo que se quiere es la Fisher-Yates aleatoria . Aquí está una implementación en Java:

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

¿Cómo funciona es que trata a todo el conjunto como un sombrero y empieza a tirar de elementos aleatorios y alineándolos en la parte delantera de la matriz. Todos los elementos son después i 'en el cubo', todos los elementos antes i se barajan.