Ich möchte einen "ultimativen Shuffle" -Algorithmus schreiben, um meine MP3-Sammlung zu sortieren

Ich suche nach Pseudocode-Vorschlägen, um meine MP3-Dateien so zu sortieren, dass Titel- und Interpretenwiederholungen vermieden werden . Ich höre Schlagersänger - Frank Sinatra, Tony Bennett, Ella Fitzgerald usw., die alte Standards singen. Jeder Künstler nimmt viele der gleichen Songs auf - Fly Me To The Moon, So sieht es heute Abend aus, Stardust usw. Mein Ziel ist es, die Songs so anzuordnen (oder die Wiedergabeliste zu bestellen), dass zwischen Künstlern und Songtiteln maximaler Abstand besteht. Wenn ich also 2000 Songs habe und 20 von Ella, würde ich sie gerne nur einmal in 100 Songs hören. Wenn 10 Künstler Fly Me To The Moon singen, würde ich es gerne einmal in 200 Songs hören. Natürlich möchte ich diese beiden Anforderungen kombinieren, um mein "ultimatives Shuffle" zu erstellen.

Ich weiß, dass dies eine ziemlich offene Frage ist. Ich habe noch nicht damit begonnen, es zu programmieren, also suche ich nur nach Vorschlägen für einen guten Ansatz. Ich habe tatsächlich einige andere Anforderungen bezüglich des gleichmäßigen Abstands anderer Songattribute, aber ich werde hier nicht darauf eingehen.

Als Ausgangspunkt ändere ich Code, den ich hier gefunden habe , um MP3-Dateien zu manipulieren und ID3-Tags zu lesen.

Ich habe eine kleine App geschrieben, die meine Bedürfnisse mit der Antwort von parsifal erfüllt. Ich schrieb auch eine Follow - up - Frage hier . Danke für all die tollen Antworten!

Möchten Sie Ihr Programm einmal ausführen und eine Wiedergabeliste erstellen oder den nächsten Song live auswählen?

In letzterem Fall ist die Antwort einfach:

• Erstellen Sie ein Array, das alle Ihre Songs mit Interpret und Titel enthält
• Erstellen Sie eine Liste (vorzugsweise eine verknüpfte Liste) für zuletzt gespielte Songtitel. Diese Liste beginnt leer, und jedes Mal, wenn Sie ein Lied abspielen, fügen Sie es der Liste hinzu. Wenn die Liste die gewünschte Größe für "Kein Song wiederholen" aufweist, löschen Sie den ältesten (ersten) Eintrag.
• Das Gleiche gilt für eine Liste von Künstlern.

Das Auswählen eines Songs erfolgt dann in der folgenden Reihenfolge:

1. Wähle zufällig ein Lied aus dem Array "Alle Lieder" aus. Dies ist nur eine Zufallszahl zwischen 0 und der Größe des Arrays.
2. Überprüfen Sie, ob der Titel bereits in der Liste der wiedergegebenen Titel enthalten ist. Wenn dies der Fall ist, kehren Sie zu Schritt 1 zurück.
3. Überprüfen Sie, ob der Künstler bereits in der Liste der wiedergegebenen Künstler enthalten ist. Wenn dies der Fall ist, kehren Sie zu Schritt 1 zurück.
4. Fügen Sie den Interpreten / Titel des Songs zu den entsprechenden Listen hinzu und löschen Sie bei Bedarf alte Einträge.
5. Spielen Sie das Lied.

Es gibt einige mögliche Probleme, die jedoch nur von Bedeutung sein sollten, wenn Sie dies als Hausaufgabe und nicht als reales Projekt ausführen.

• Wie @Dukeling in einem Kommentar sagte, geraten Sie möglicherweise in eine Schleife, in der Sie ständig Songs ablehnen, wenn Ihre Sammlung zugunsten eines einzelnen Künstlers oder Songtitels dramatisch aus dem Gleichgewicht gerät. In der Praxis wird dies kein Problem sein. Die Lösung ist, dass Sie die Größe der "bereits gesehenen" Listen reduzieren müssen. Durch Hinzufügen von Zählern in den Schritten 2 und 3 können Sie feststellen, ob es sich um ein Problem handelt (wenn Sie 10 Fehler hintereinander sehen, geben Sie eine Warnung aus und / oder verringern Sie die Größe der Liste).
• Wenn Sie versuchen, eine Wiedergabeliste zu erstellen, die alle Ihre nur einmal abgespielten Titel enthält, müssen Sie die Titel aus dem Quell-Array entfernen. Dies ändert auch, wie Sie mit zu vielen "kürzlich gespielten" Fehlern umgehen (weil Sie möglicherweise nur einen Künstler in Ihrem Quell-Array haben).
• Wenn Ihre ID3-Tags wie meine sind, enthalten sie viele Rechtschreibfehler. Muss "Duke Ellington" anders sein als "Duke Elingten"? Wenn ja, prüfen Sie die Verwendung eines Levenstein-Matchers beim Scannen der "zuletzt gespielten" Listen.

Ich habe so etwas gemacht, bevor ich einen Generator verwendet habe (in C # eine Endlosschleife, die yieldjede Schleifeniteration ist). Bei jeder Iteration wird der Pool von Songs (oder was auch immer) überprüft und zu kürzlich gespielte Songs (oder was auch immer negative Kriterien) herausgefiltert. Dann wählen Sie eine aus der gefilterten Liste aus und aktualisieren Ihren Status. Während sich Ihr Status verschiebt (Sie spielen Nicht-Sinatra-Songs), werden die Kriterien aufgehoben und Ihre ausgeschlossenen Songs werden wieder aufgenommen.

Natürlich gibt es Eckfälle, mit denen man sich befassen muss:

• Was passiert, wenn du alle Songs rauswirfst? (in der Regel nur eine zufällig auswählen, in der Hoffnung, den Zustand zu destabilisieren)
• Sollten einige Kriterien bevorzugt werden? (Normalerweise möchten Sie vielleicht nicht Fly Me to the Moon hintereinander spielen und würden es vorziehen, Sinatra nicht hintereinander zu spielen, aber wenn das alles ist, was Sie haben ...)
• Was passiert, wenn Ihre Songsammlung mitten im Kampf aktualisiert wird? (In der Regel einfach zu handhaben, kann jedoch je nach Verwendung zu Problemen führen.)

Wenn Sie die Ausreißer Ihrer Frage, die Telastyn vorbringt, ignorieren, scheint es, als hätten Sie eine Variation des Rucksackproblems . Zum Glück ist es ein ziemlich gut dokumentierter Algorithmus.

Aus Wikipedia

Bestimmen Sie bei einer gegebenen Menge von Elementen, die jeweils ein Gewicht und einen Wert haben, die Anzahl der Elemente, die in eine Sammlung aufgenommen werden sollen, so, dass das Gesamtgewicht kleiner oder gleich einem gegebenen Grenzwert ist und der Gesamtwert so groß wie möglich ist.

In diesem Artikel sind einige potenziell relevante Variationen sowie eine zusätzliche Liste mit Rucksackproblemen aufgeführt

Eine Variation des Rucksackproblems ist das Mehrziel-Rucksackproblem. Der Ant Colony- Algorithmus wird vorgeschlagen, um dieses Problem zu lösen. Der Ansatz der Ameisenkolonie ist für Sie möglicherweise der einfachste Weg, die NP-harten Aspekte Ihrer Frage zu umgehen.

Ich könnte Ihr Problem auch als eine extreme Variante des Problems des Handlungsreisenden betrachten . Jede zu besuchende Stadt ist wirklich ein Lied, das Sie spielen möchten, aber ich bin mir nicht sicher, wie Sie die Intervalle zwischen Künstlern festlegen würden. Dieser Vorschlag steht auch im Zusammenhang mit dem Ansatz der Ameisenkolonie.

Ich arbeite unter der Annahme, dass dies ein "Hier ist meine Bibliothek, führe dieses Programm aus und erstelle einen Befehl zum Abspielen der Songs."

Dies wurde nicht implementiert und ich bin mir nicht sicher, wie gut es sein Mischen durchführen wird. Es kann sein, dass ich im Filter etwas zu streng bin , was (glaube ich) zu einer vorgeschriebenen Reihenfolge für den Rest führen würde, wenn eine anfängliche Reihe von Liedern gegeben wäre.

Man hat einen ideal_gapHasch. Dies berechnet sich aus der Dichte eines Songs mit einer bestimmten Eigenschaft (Künstler, Album, Titel). Wenn man 2000 Songs hat und 20 davon von einem Künstler namens Ella sind, ideal_gap{'artist'}{"ella"}wären das 100.

Mit diesen Informationen hat man auch das Maximum der ideal_gap-Werte. Nennen wir das max_gap.

Bedenken Sie: ideal_gapGeben Sie den Maximalwert an, um zu verhindern, dass ein Titel, den nur zwei Interpreten gesungen haben, 1000 Titel später wiedergegeben wird, und erhöhen Sie den Wert für max_gap drastisch, was zu vielen Iterationen von "Zurück, keine Titel, zurück" führt Aus, keine Lieder ".

Untersucht man die zuletzt gespielten max_gap-Songs (dies kann aus einem vorherigen Durchgang stammen, so dass, wenn Frank Sinatra Fly Me To The Moon singt, der nächste Durchgang nicht zufällig mit dem gleichen Song beginnt), werden die Songs herausgefiltert Die Bibliothek führt zu einer Reihe von Kandidatenliedern. Ein Lied würde sich nur in den Kandidatenliedern befinden, wenn alle seine Lücken kleiner als die ideal_gapfür diese Eigenschaften sind.

Wählen Sie aus der Liste der Titelkandidaten einen zufällig aus.

Bedenken Sie: Gewichtung des Sets, damit Songs, die eine höhere maximale Lücke aufweisen, mit größerer Wahrscheinlichkeit gewichtet werden. Auf diese Weise werden am Ende der Wiedergabeliste nicht alle Songs mit größerer maximaler Lücke angehäuft.

Bedenken Sie: Anstatt alle drei Eigenschaften größer als die ideale Lücke zu haben, sind es nur zwei von drei. Dies kann bedeuten, dass etwas früher als das ideale Ideal gespielt werden könnte, erhöht jedoch die Größe des Kandidaten-Songsets, was bedeutet, dass das "zufällige auswählen" mehr Optionen hat.

Wenn keine Songs vorhanden sind, die die Anforderungen erfüllen, setzen Sie den max_gapWert um 1 zurück und alle ideal_gaps in n/max_gapProzent, wobei angegeben nwird, wie oft dieser Wert zurückgesetzt wurde. Auf diese Weise würde bei max_gapeinem Wert von 100, der in dieser Iteration fünfmal zurückgesetzt wurde, eine ideale_Lücke von 100 vorübergehend auf 95 und eine ideale_Lücke von 20 vorübergehend auf 19 eingestellt Lücke, bis es mindestens einen Kandidaten-Song gibt, und wähle ihn dann wie oben aus.

Bedenken Sie: Haben Sie eine minimale Poolgröße. Dies erhöht die Varianz, kann jedoch dazu führen, dass ein Lied früher als die ideale Lücke abgespielt wird, wenn es ein anderes Lied gibt, das abgespielt werden könnte.

Dies ist ein Optimierungsjob, und ein ziemlich komplexer Job, wenn Sie nach der optimalen Lösung suchen . Zum Glück glaube ich, dass es einer dieser Fälle ist, in denen das Gute gut genug ist.

Als Erstes müssen Sie ein mathematisches Qualitätskriterium festlegen, dh eine Formel, die bei einer Permutation der Liste eine einzelne Zahl zurückgibt, die beschreibt, wie gut oder schlecht diese Permutation ist.

Ein einfacher Formelvorschlag. Jedes Kriterium, das Sie berücksichtigen möchten, sollte gewichtet werden. Wichtige Kriterien sollten mit einem hohen Gewicht und Kriterien mit einem niedrigen Gewicht versehen werden, bei denen viele Songs dieselbe Eigenschaft haben, damit diese nicht dominieren :

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

Je niedriger der Wert, den diese Prozedur erzeugt, desto besser ist die Listenpermutation.

Permutation machen

Jetzt können Sie diese Formel in math.stackexchange übernehmen und sich sagen lassen, wie wahnsinnig schwierig und möglicherweise praktisch unmöglich es ist, für alles andere als eine unbedeutende Anzahl von Songs die optimale Lösung zu finden, oder Sie werfen einfach Taktzyklen darauf und erhalten eine gute Lösung.

Es gibt viele Möglichkeiten, dies zu tun. Hier ist eine:

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

Dies ist ein etwas verschwenderischer Algorithmus, der jedoch leicht zu implementieren ist und mit so vielen Kriterien wie gewünscht umgehen kann.

Optimierungen

Es können viele verschiedene Optimierungen und Optimierungen vorgenommen werden, hier einige:

Prüfen Sie bei der Berechnung des Qualitätswerts keinen Titel mit jedem anderen Titel in der Liste, sondern nur mit den etwa 100 nächsten Titeln. Bei gängigen Werten hat diese Geschwindigkeitsoptimierung praktisch keinen Einfluss auf die Qualität des Ergebnisses.

Für einen seltenen Wert einer bestimmten Eigenschaft ist es möglicherweise effizienter, die vorhandenen Instanzen dieses Werts zu verfolgen, als nach ihnen zu suchen.

Wenn Sie der Meinung sind, dass es wichtig ist, dass Werte mit wenigen Instanzen nicht nur weit voneinander entfernt sind, sondern in der Nähe der Gerade, ist es wahrscheinlich erforderlich, die Gewichtung für diese spezifischen Werte zu erhöhen, jedoch nicht für andere Werte dieses Kriteriums.

Eine Pseudozufallsfunktion, die alle möglichen Paare in gleicher Verteilung aus der Liste auswählt, hat möglicherweise eine etwas bessere Effizienz pro Auswahl als eine normale Zufallsauswahl.

Es ist interessant, welche unterschiedlichen Ansätze die Menschen verfolgen. Ich würde Folgendes tun:

Geben Sie auf der Grundlage aller bisher gespielten Titel jeweils eine Punktzahl an. Spielen Sie den Titel mit der niedrigsten Punktzahl (oder bei identischen Punktzahlen eine zufällige, die der niedrigsten Punktzahl entspricht). Wiederholen.

Das Schwierige ist natürlich, eine Wertung abzugeben. Für jeden möglichen Titel, den Sie möglicherweise als Nächstes spielen, müssen Sie jeden Titel (oder eine begrenzte Anzahl von Titeln) durchgehen, den Sie bereits gespielt haben. Wenn der [mögliche nächste] Titel und der [zuletzt gespielte] Titel etwas gemeinsam haben, fügen Sie dem Score hinzu, je nachdem, wie viel sie gemeinsam haben, was sie gemeinsam haben und wie lange der [zuletzt gespielte] Titel zurückliegt gespielt. Sie möchten wahrscheinlich, dass "überhaupt nichts gemeinsam ist" 0 ist, sodass Sie mit allen Spuren als 0 beginnen können.

Sie werden wahrscheinlich zuerst mit einigen handgefertigten Wiedergabelisten experimentieren wollen, um die Mathematik richtig zu machen - möchten Sie die Anzahl der Wörter gemeinsam oder das Quadrat der Anzahl der Wörter gemeinsam oder die Quadratwurzel der Zahl von Wörtern gemeinsam? Führen Sie Ihre gesamte Wiedergabeliste durch, sehen Sie, welche am häufigsten verwendet werden, und optimieren Sie die Faktoren von Hand, um das richtige Gleichgewicht zu erzielen. Vielleicht möchten Sie per Brief gehen, also hat "Duke Ellington" eine hohe Punktzahl im Vergleich zu "Duke Elington", aber eine noch höhere Punktzahl im Vergleich zu "King Elle Duton" (wenn ich keine Buchstaben verloren habe :) . Sie sollten sehr sorgfältig überlegen, welche Felder Sie vergleichen möchten und ob Sie zwischen Feldern vergleichen möchten. Sie könnten sogar Bigramme (Buchstabenpaare) in Betracht ziehen, im Fall von Duke ellington "Du", "

Beachten Sie, dass, wenn Sie viele bestimmte Interpreten haben, dieser Interpreten möglicherweise vorrangig abgesetzt wird - Sie hören möglicherweise fünfmal einen Titel eines einzelnen Interpreten, bevor Sie alle zehn Ihrer Duke Ellington-Titel hören. Dies könnte oder könnte nicht das sein, was Sie wollen. Sie können dies vermeiden, indem Sie ein Wörterbuch für alles einrichten, was Sie vergleichen müssen, und für die Häufigkeit des Auftretens. Wenn Sie also viele Duke Ellington-Titel haben, sind zwei Titel von Duke Ellington "weniger ähnlich" als zwei von Billy Joe Shaver .

Es könnte sich sogar lohnen, mit jeder Kombination von zwei Liedpaaren einen Tisch vorzuberechnen. Wenn Sie überlegen, welches Lied Sie als nächstes spielen möchten, müssen Sie sich nur das beste Lied merken, das Sie bisher gespielt haben. Wenn der nächste zu berücksichtigende Titel eine schlechtere Punktzahl aufweist als der bisher beste Titel, können Sie mit dem nächsten Titel fortfahren.