J'aimerais écrire un algorithme «ultime shuffle» pour trier ma collection de mp3

Je recherche des suggestions de pseudocodes pour trier mes fichiers mp3 de manière à éviter les répétitions de titres et d'artistes . J'écoute des crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald, etc., qui chantent de vieilles normes. Chaque artiste enregistre plusieurs des mêmes chansons - Volez-moi sur la lune, Ce que vous regardez ce soir, Stardust, etc. Mon objectif est d'organiser les chansons (ou de commander la liste de lecture) avec le maximum d'espace entre les artistes et les titres des chansons. Donc, si j'ai 2000 chansons et 20 sont de Ella, j'aimerais ne l'entendre qu'une fois sur 100. Si 10 artistes chantent Fly Me To The Moon, j'aimerais l'entendre une fois sur 200 chansons. Bien sûr, je veux combiner ces deux exigences pour créer mon "mélange ultime".

Je sais que la question est assez ouverte. Je n'ai pas encore commencé à le programmer, alors je cherche simplement des suggestions pour une bonne approche. J'ai en fait d'autres exigences concernant l'espacement régulier des autres attributs de la chanson, mais je n'entrerai pas dans les détails ici.

Comme point de départ, je modifie le code que j'ai trouvé ici pour manipuler des fichiers mp3 et lire les tags ID3.

J'ai écrit une petite application qui répond à mes besoins en utilisant la réponse de parsifal ci-dessous. J'ai aussi écrit une question de suivi ici . Merci pour toutes les bonnes réponses!

Voulez-vous exécuter votre programme une fois et générer une liste de lecture ou choisir la chanson suivante en direct?

Si ce dernier cas, la réponse est simple:

• Créez un tableau contenant toutes vos chansons, avec artiste et titre.
• Créez une liste (une liste chaînée est préférable) pour contenir les titres de chansons récemment joués. Cette liste est vide au début et chaque fois que vous jouez une chanson, vous l'ajoutez à la liste. Lorsque la liste affiche la taille souhaitée "pas de répétition de chanson", supprimez la plus ancienne (première) entrée.
• Idem pour une liste d'artistes.

Choisir une chanson devient alors la séquence d'étapes suivante:

1. Choisissez au hasard une chanson dans le tableau "toutes les chansons". Ceci est juste un nombre aléatoire compris entre 0 et la taille du tableau.
2. Voir si cette chanson est déjà dans la liste des chansons jouées. Si c'est le cas, revenez à l'étape 1.
3. Voir si l'artiste est déjà dans la liste des artistes joués. Si c'est le cas, revenez à l'étape 1.
4. Ajoutez l'artiste de la chanson / le titre aux listes appropriées, en supprimant les anciennes entrées si nécessaire.
5. Joue la chanson.

Il y a plusieurs problèmes possibles, mais ils ne devraient avoir d'importance que si vous faites cela comme un devoir et non comme un vrai projet.

• Comme @Dukeling l'a dit dans un commentaire, si votre collection est radicalement déséquilibrée au profit d'un seul artiste ou d'un seul titre de chanson, vous risquez de vous perdre dans une boucle où vous rejetez constamment des chansons. En pratique, cela ne sera pas un problème. La solution consiste à réduire la taille des listes "déjà vues". Et l'ajout de compteurs aux étapes 2 et 3 peut vous dire si c'est un problème (si vous voyez 10 échecs à la suite, déclenchez un avertissement et / ou réduisez la taille de la liste).
• Si vous essayez de créer une liste de lecture contenant toutes vos chansons jouées une seule fois, vous devez supprimer des chansons de la matrice source. Cela changera également la façon dont vous traitez avec trop d'échecs "récemment joués" (parce que vous pourriez éventuellement vous retrouver avec un seul artiste dans votre tableau source).
• Si vos tags ID3 ressemblent au mien, ils contiennent de nombreuses erreurs d’orthographe. Est-ce que "Duke Ellington" doit être différent de "Duke Elingten"? Si c'est le cas, envisagez d'utiliser un matcher Levenstein lorsque vous parcourez les listes "récemment jouées".

J'ai déjà fait quelque chose comme cela avant d'utiliser un générateur (en C #, une boucle infinie qui correspond à yieldchaque itération de boucle). Chaque itération examine son pool de chansons (ou autre) et rejette celles qui ont été jouées trop récemment (ou quels que soient les critères négatifs). Ensuite, vous en choisissez un dans la liste filtrée et mettez votre état à jour. Au fur et à mesure que votre état évolue (vous jouez des chansons non-Sinatra), les critères s'effondrent et vos chansons exclues commencent à être ré-incluses.

Bien sûr, il y a des cas à traiter:

• Qu'est-ce qui se passe si vous jetez toutes les chansons? (généralement en choisir un au hasard, dans l’espoir de déstabiliser l’État)
• Certains critères devraient-ils être préférés? (Habituellement, vous ne voulez peut-être pas jouer Fly Me to the Moon dos à dos et préférez ne pas jouer Sinatra, mais si c'est tout ce que vous avez ...)
• Que se passe-t-il si votre collection de chansons est mise à jour en cours de combat? (généralement facile à gérer, mais la simultanéité peut poser problème en fonction de l'utilisation)

En ignorant les valeurs aberrantes de votre question soulevées par Telastyn, il semble que vous ayez une variation du problème du sac à dos . Heureusement, c'est un algorithme assez bien documenté.

De Wikipedia

Pour un ensemble d’articles, chacun avec un poids et une valeur, déterminez le nombre d’articles à inclure dans une collection afin que le poids total soit inférieur ou égal à une limite donnée et que la valeur totale soit aussi grande que possible.

Certaines variantes potentiellement pertinentes sont répertoriées dans cet article, ainsi qu'une liste supplémentaire de problèmes de sac à dos.

Une variante du problème de sac à dos est le problème de sac à dos à objectifs multiples. L' algorithme de colonie de fourmis est suggéré comme moyen de résoudre ce problème. L’approche «colonie de fourmis» pourrait être le moyen le plus simple d’éviter les aspects difficiles de votre question.

Je pourrais aussi voir en considérant votre problème comme une variante extrême du problème du voyageur de commerce . Chaque ville à visiter est vraiment une chanson que vous voulez jouer, mais je ne sais pas comment vous définiriez les intervalles entre les artistes. Cette suggestion est également liée à / peut être résolue par l'approche de colonie de fourmis.

Je pars du principe que c’est un "voici ma bibliothèque, lancez ce programme et générez un ordre pour jouer les chansons".

Cela n’a pas été mis en œuvre et je ne sais pas dans quelle mesure il réussira à le remanier. Il se peut que je sois un peu trop strict dans le filtre, ce qui résulterait (je crois) en un ordre prescrit pour le reste, à partir d’un ensemble initial de chansons.

On a un ideal_gaphash. Ceci est calculé par la densité d'une chanson avec une propriété donnée (artiste, album, titre). Si on a 2000 chansons et que 20 d’entre elles ont été écrites par un artiste nommé Ella, ideal_gap{'artist'}{"ella"}c’est 100.

En ayant cette information, on a aussi le maximum des valeurs ideal_gap. Appelons cela max_gap.

Considérez: avoir un maximum de ideal_gapvaleur pour empêcher une chanson que seulement deux artistes ont chantée d'empêcher l'autre chanson d'être jouée plus de 1000 chansons plus tard, et d'augmenter considérablement la valeur max_gap, ce qui entraîne de nombreuses itérations de "retour, pas de chanson, retour off, pas de chansons ".

Examiner les dernières chansons de max_gap jouées (ceci peut être rempli à partir d’une exécution précédente. Ainsi, si elle termine avec Frank Sinatra en train de chanter Fly Me To the Moon, la prochaine exécution ne commencera pas par la même chanson par hasard), on filtre les chansons la bibliothèque résultant en un ensemble de chansons candidates. Une chanson ne sera dans les chansons candidates que si toutes ses lacunes sont inférieures à ideal_gapcelles de ces propriétés.

Dans l'ensemble des chansons candidates, sélectionnez-en une au hasard.

Considérez: pondérez l’ensemble pour que les chansons qui attribuent un écart maximal plus élevé soient plus probables. De cette façon, tous les morceaux de max gap les plus grands ne s'empilent pas à la fin de la liste de lecture.

Considérez: au lieu que les trois propriétés soient plus grandes que l’espace idéal, il n’ya que deux sur trois. Cela peut signifier que quelque chose pourrait être joué plus tôt que l'idéal idéal, mais augmente la taille de l'ensemble de morceaux candidats, ce qui signifie que "choisir au hasard" a plus d'options.

S'il n'y a pas de chansons qui remplissent les conditions requises, max_gapannulez le par 1 et tous les idéal_gaps par n/max_gappour cent où nest le nombre de fois que cela a été annulé. De cette façon, s'il existe un nombre max_gapde 100 et qu'il a été réduit de 5 fois dans cette itération, un écart idéal de 100 serait ajusté temporairement à 95 et un écart idéal de 20 serait temporairement de 19. Répéter espace jusqu’à ce qu’il y ait au moins une chanson candidate, puis sélectionnez-la comme ci-dessus.

Considérez: avoir une taille de piscine minimale. Cela ajoute à la variance, mais peut avoir pour conséquence qu’une chanson est jouée plus tôt que l’espace idéal lorsqu’une autre chanson peut être jouée.

Il s’agit d’un travail d’optimisation et assez complexe si vous recherchez la solution optimale. Heureusement, je crois que c’est l’un de ces cas où l’assez bon suffira.

La première chose à faire est d’établir un critère de qualité mathématique, c’est-à-dire une formule qui, étant donné une permutation de la liste, renverra un nombre unique décrivant si cette permutation est bonne ou mauvaise.

Une suggestion de formule simple, attribuez un poids à chaque critère que vous souhaitez prendre en compte, accordez un poids élevé aux critères importants et peu aux critères dans lesquels beaucoup de chansons partagent la même propriété, de sorte que celles-ci ne dominent pas :

For each song on the list
    For each other song on the list
        For each criteria
            If the two songs share that criteria
                Add to the quality value: square root( [criteria weight]/[distance between the two songs] )

Plus la valeur de cette procédure est faible, meilleure est la permutation de liste.

Faire la permutation

Maintenant, vous pouvez utiliser cette formule dans math.stackexchange et lui demander de vous dire combien il est incroyablement difficile et pratiquement impossible de trouver la solution optimale bonne solution.

Il y a plusieurs façons de le faire, en voici une:

Start with a random permutation of the list.
Several million times do the following:
    Select two entries at random
    For each of those two entries calculate their contribution to the quality value
    Swap the positions of the two entries
    Calculate the contribution to the quality value of the two entries at their new position
    If the sum of the calculations in the new positions is greater than the sum in the old positions
        Swap back

Il s’agit d’un algorithme peu rentable, mais il est facile à mettre en œuvre et peut traiter autant de critères qu’on le souhaite.

Optimisations

Des charges de différents réglages et optimisations peuvent être appliquées, en voici quelques unes:

Dans le calcul de la qualité, ne cherchez pas à comparer une chanson avec toutes les autres chansons de la liste, comparez-la simplement aux 100 chansons les plus proches. Pour les valeurs communes, cette optimisation de la vitesse n'a pratiquement aucune influence sur la qualité du résultat.

Pour une valeur rare d'une propriété donnée, il peut être plus efficace de suivre les instances existantes de cette valeur que de les rechercher.

Si vous estimez qu'il est important que les valeurs qui ont peu d'instances soient proches les unes des autres plutôt que très proches, il est probablement nécessaire d'augmenter le poids de ces valeurs spécifiques, mais pas des autres valeurs de ce critère.

Une fonction pseudo-aléatoire qui sélectionne toutes les paires possibles de la liste à distribution égale peut avoir une efficacité légèrement supérieure par sélection par rapport à une sélection aléatoire normale.

Il est intéressant de voir les différentes approches adoptées par les gens. Je ferais ce qui suit:

Sur la base de toutes les pistes jouées jusqu'à présent, attribuez à chacun un score. Jouez la piste avec le score le plus bas (ou, dans le cas de scores identiques, une piste aléatoire correspondant au score le plus bas). Répéter.

La difficulté, bien sûr, est de donner un score. Pour chaque piste possible que vous pourriez jouer ensuite, vous devrez parcourir chacune des pistes (ou un nombre limité) de pistes que vous avez déjà lues. Si la piste [possible suivante] et la piste [récemment jouée] ont quelque chose en commun, vous ajoutez à la partition, en fonction de leur nombre de points communs, de ce qu’ils ont en commun et de la date de la précédente lecture de la piste [jouée récemment]. joué. Vous voudriez probablement que "rien du tout en commun" soit 0, vous pouvez donc commencer avec toutes les pistes en tant que 0.

Vous voudrez probablement expérimenter avec des listes de lecture créées à la main pour commencer, pour obtenir des calculs exacts - voulez-vous le nombre de mots en commun, ou le carré du nombre de mots en commun, ou la racine carrée du nombre de mots en commun? Parcourez toute votre liste de lecture, identifiez celles qui semblent "les plus communes" et réglez à la main les facteurs pour obtenir le bon équilibre. Peut-être que vous voulez aller par lettre, alors "Duke Ellington" a un score élevé par rapport à "Duke Elington", mais un score encore plus élevé par rapport à "King Elle Duton" (si je n'ai pas perdu de lettres :) . Vous devez examiner très attentivement les champs que vous souhaitez comparer et indiquer si vous souhaitez comparer des champs. Vous pourriez même envisager des bigrammes (paires de lettres; dans le cas de Duke Ellington, "Du", "

Notez que, si vous avez beaucoup d'artistes en particulier, cet artiste peut être classé en priorité - vous pouvez entendre un morceau par un artiste unique 5 fois, avant d'entendre les 10 morceaux de votre Duke Ellington. Cela peut être ou ne pas être ce que vous voulez. Vous pouvez éviter cela en créant un dictionnaire de tout ce que vous devez comparer et de la fréquence à laquelle ils apparaissent. Si vous avez beaucoup de morceaux de Duke Ellington, deux morceaux de Duke Ellington sont "moins similaires" que deux de Billy Joe Shaver. .

Cela vaut même peut-être la peine de pré-calculer une table avec chaque combinaison de deux paires de chansons. En outre, pour déterminer quelle chanson jouer ensuite, il vous suffit de vous souvenir de la meilleure chanson à ce jour. si le prochain à prendre en compte a un score inférieur à celui de la meilleure chanson à ce jour, vous pouvez passer au suivant.