Un moyen efficace de randomiser un tableau - le code aléatoire

Question

On m'a posé cette question dans une interview et j'ai donné diverses solutions, mais l'intervieweur n'a pas été convaincu. Je suis intéressé à trouver une solution. S'il vous plaît jeter votre point de vue:

Q: Ecrire une structure de données efficace pour mettre en œuvre le shuffle dans un iPod. Il doit jouer toutes les chansons, chaque fois dans un ordre différent au hasard, ne doit pas se répéter la même chanson. (La plupart du temps en O (n))

Une solution, je pensais au bout de l'entrevue: Je peux faire un tri rapide randomisé sans récursivité. Où nous au hasard, choisi 1 pivot O (1), puis faire le tri rapide O (n). Maintenant, les chansons seront classés dans un ordre et je les jouer jusqu'à la fin. Une fois qu'il atteint la fin, je vais à nouveau choisir un pivot aléatoire et répéter ce processus encore et encore.

Cordialement, Sethu

Answer 1

Placez toutes les chansons dans un tableau ... Pour chaque élément de la matrice de permutation avec une position aléatoire.

Answer 2

Vous voulez que le Fisher-Yates Shuffle . Soyez conscient des erreurs de mise en œuvre mentionnées sur cette page, comme votre réponse actuellement acceptée tombe sous le coup d'un.

Answer 3

Eh bien, la première solution à temps linéaire qui vient à l'esprit:

Vous pourriez faire une liste chaînée de toutes les chansons, ce qui prendrait environ O (n) (étant donné que les insertions sont des opérations de temps constants). Ensuite, générer un nombre aléatoire, modulo la taille de la liste pour obtenir un index aléatoire et supprimer cet index et l'ajouter à une nouvelle liste (qui sont tous deux opérations de temps constants).

Une insertion pour chaque O (n) + un retrait pour chacun O (n) + une seconde insertion O (n). Cela conduirait à une solution globale de temps linéaire.

Modifier : J'ai complètement oublié de marcher la liste. Ainsi, au lieu, vous pouvez faire le résultat d'un tableau de longueur fixe. Pop la tête de la liste chaînée, lui attribuer l'indice aléatoire, et remplir le tableau.

Answer 4

Nate algorithmes'S (édité) et Brian sont les Fisher-Yates aléatoire O (n), alors que le tri est par brassage O (nlogn), mais peut effectivement être plus rapide dans la pratique (http://en.wikipedia.org/wiki / Fisher% E2% 80% 93Yates_shuffle # Comparison_with_other_shuffling_algorithms). Obtenir mal traînante chanson peut avoir des conséquences insignifiantes, mais si vous écrivez un algorithme de mélange pour un jeu de poker en ligne, assurez-vous que vous savez ce que vous faites (http://www.cigital.com/news/index.php?pg= art & artid = 20).

Answer 5

Je suis un débutant, laissez-moi dire une solution qui frappe à l'esprit, si quelque chose ne va pas s'il vous plaît me faire connaître.

permet d'assumer les titres sont stockées dans la liste soit liée simple ou double. Chaque fois que le lecteur de musique est ouvert choisir un nombre aléatoire inférieur (tout numéro désiré) prendre k, et inverse, tous les nœuds k dans la liste, faites de la même deux fois ou trois fois maximum (comme vous le souhaitez) qui prendrait O ( 2n) ou O (3n) le temps de lecture aléatoire. enfin avoir un pointeur sur le dernier noeud de la liste. Et chaque fois qu'une chanson est écoutée (un nœud est visité) supprimer le nœud et l'insérer à côté du dernier nœud qui peut être fait en O (1) temps. Cela continue jusqu'à ce que le lecteur de musique est fermé.

Merci, Désireuse de connaître l'exactitude de la réponse.

Answer 6

Ce que vous voulez est le Fisher-Yates aléatoire . Voici une implémentation 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 */

Comment ça marche? Est-il traite tout le réseau comme un chapeau et commence à tirer des éléments aléatoires et en les alignant à l'avant du tableau. Tous les éléments après i sont « dans le seau », tous les éléments avant i sont mélangés.