Mi piacerebbe scrivere un algoritmo "ultimate shuffle" per ordinare la mia collezione mp3

Vuoi eseguire il tuo programma una volta e generare una playlist, o scegliere la prossima canzone dal vivo?

Se quest'ultimo, la risposta è semplice:

• Crea un array che contiene tutti i tuoi brani, con artista e titolo
• Crea una lista (lista collegata preferibile) per conservare i titoli dei brani riprodotti di recente. Questo elenco inizia vuoto e ogni volta che riproduci un brano lo aggiungi all'elenco. Quando la lista tocca la dimensione "nessuna ripetizione brano" desiderata, rilascia la voce più vecchia (prima).
• Idem per un elenco di artisti.

Scegliere una canzone diventa la seguente sequenza di passaggi:

1. Seleziona in modo casuale una canzone dall'array "all songs". Questo è solo un numero casuale compreso tra 0 e la dimensione dell'array.
2. Verifica se quella canzone è già presente nell'elenco delle canzoni riprodotte. In questo caso, torna al passaggio 1.
3. Verifica se l'artista si trova già nell'elenco degli artisti riprodotti. In questo caso, torna al passaggio 1.
4. Aggiungi l'artista / titolo del brano agli elenchi appropriati, eliminando le voci precedenti se necessario.
5. Riproduci la canzone.

Ci sono un paio di possibili problemi, ma dovrebbero avere importanza solo se stai facendo questo come compiti a casa e non come un vero progetto.

• Come ha detto @Dukeling in un commento, se la tua raccolta è drammaticamente sbilanciata a favore di un singolo artista o titolo di canzone, potresti entrare in un ciclo in cui rifiuti costantemente le canzoni. In pratica, questo non sarà un problema. La soluzione è che è necessario ridurre la dimensione degli elenchi "già visti". E l'aggiunta di contatori nei passaggi 2 e 3 può dirti se si tratta di un problema (se vedi 10 errori in una riga, genera un avviso e / o riduci le dimensioni dell'elenco).
• Se stai provando a produrre una playlist che contiene tutte le tue canzoni riprodotte una sola volta, dovrai rimuovere i brani dall'array di origine. Questo cambierà anche il modo in cui gestisci troppi guasti "giocati di recente" (perché alla fine potresti finire con un solo artista nella tua matrice sorgente).
• Se i tag ID3 sono come il mio, contengono molti errori di ortografia. "Duke Ellington" ha bisogno di essere diverso da "Duke Elingten"? In caso affermativo, cerca di utilizzare un correttore Levenstein durante la scansione degli elenchi "riprodotti di recente".

Ho fatto qualcosa del genere prima di usare un generatore (in C #, un ciclo infinito che yield s ogni iterazione del ciclo). Ogni iterazione guarda al suo gruppo di canzoni (o qualsiasi altra cosa) e lancia fuori quelle che sono state giocate troppo recentemente (o qualunque criterio negativo). Quindi ne selezioni uno dall'elenco filtrato e aggiorni il tuo stato. Quando il tuo stato va alla deriva (suoni brani non di Sinatra), i criteri scomposti e le tue canzoni escluse vengono ricomposte.

Ovviamente ci sono casi d'angolo da affrontare:

• Cosa succede se butti fuori tutte le canzoni? (di solito ne scegli uno a caso, sperando di destabilizzare lo stato)
• Dovrebbero essere preferiti alcuni criteri? (di solito, forse non vuoi giocare a Fly Me to the Moon back to back, e preferiresti non suonare Sinatra back to back, ma se è tutto ciò che hai ...)
• Che cosa succede se la tua raccolta di brani viene aggiornata a metà combattimento? (Di solito facile da gestire, ma la concorrenza potrebbe avere problemi a seconda dell'utilizzo)

Ignorando i valori anomali della tua domanda sollevata da Telastyn, sembra che tu abbia una variazione nel problema nello zaino . Fortunatamente, è un algoritmo abbastanza ben documentato.

Da Wikipedia

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Ci sono alcune varianti potenzialmente rilevanti elencate in quell'articolo insieme a un elenco di problemi dello zaino

Una variazione del problema dello zaino è il problema dello zaino multi-obiettivo. L'algoritmo ant colon è suggerito come mezzo per risolvere questo problema. L'approccio alla colonia di formiche potrebbe essere il modo più semplice per evitare gli aspetti NP-difficili della tua domanda.

Potrei anche vedere considerando il tuo problema come una variante estrema del problema venditore ambulante . Ogni città da visitare è davvero una canzone che si desidera riprodurre, ma non sono sicuro di come specificare gli intervalli tra gli artisti. Questo suggerimento è anche correlato a / può essere risolto con l'approccio della colonia di formiche

Sto lavorando partendo dal presupposto che questo è un "ecco la mia libreria, esegui questo programma e generi un ordine per riprodurre i brani".

Questo non è stato implementato e sono incerto su quanto bene preformerà il suo mescolamento. Può darsi che io sia un po ' too strict nel filtro, il che risulterebbe (credo) in un ordine prestabilito per il resto, dato un insieme iniziale di canzoni.

Uno ha un hash ideal_gap . Questo è calcolato dalla densità di una canzone con una determinata proprietà (artista, album, titolo). Se uno ha 2000 canzoni e 20 di loro sono di un artista di nome Ella, ideal_gap{'artist'}{"ella"} sarebbe 100.

Avendo questa informazione si ha anche il massimo dei valori ideal_gap. Chiamiamo questo max_gap .

Considera: avere un valore massimo per il ideal_gap per evitare che una canzone che solo due artisti hanno cantato impedisca che l'altra canzone venga riprodotta 1000 canzoni più tardi, e anche aumentando drasticamente il valore max_gap risultante in molte iterazioni di "indietro" spento, niente canzoni, indietro, niente canzoni ".

Esaminando le ultime canzoni di max_gap giocate (questo può essere popolato da una precedente esecuzione in modo che se finisse con Frank Sinatra che canta Fly Me To the Moon, la prossima esecuzione non inizierà con la stessa canzone per caso), un filtro canzoni fuori dalla libreria risultanti in un insieme di canzoni candidate. Una canzone si trova solo nelle canzoni candidate se tutte le sue lacune sono inferiori al ideal_gap per tali proprietà.

Dal set di canzoni candidate, selezionane una a caso.

Considera: ponderare il set in modo che le canzoni che attribuiscono un gap massimo più alto siano ponderate per essere più probabili. In questo modo, uno non ha tutti i più grandi brani di gap massimo accumulati alla fine della playlist.

Considera: invece di avere tutte e tre le proprietà più grandi del gap ideale, solo due su tre. Ciò potrebbe significare che qualcosa potrebbe essere riprodotto prima dell'ideale ideale, ma aumenta le dimensioni del set di canzoni candidate, il che significa che "sceglierne uno a caso" ha più opzioni.

Se non ci sono brani che soddisfano i requisiti, retrocedi max_gap di 1 e tutti ideal_gaps di n/max_gap percento dove n è il numero di volte in cui questo è stato annullato. In questo modo se c'è un max_gap di 100, ed è stato eseguito il back off per 5 volte in questa iterazione, un ideal_gap di 100 sarebbe regolato per essere temporaneamente 95, e un ideal_gap di 20 sarebbe regolato per essere temporaneamente 19. Ripeti allontanando il gap finché non c'è almeno una canzone candidata, quindi selezionala come sopra.

Considera: avere una dimensione minima del pool. Ciò aumenta la varianza, ma può comportare che una canzone venga riprodotta prima del divario ideale quando c'è un'altra canzone che può essere riprodotta.

Questo è un lavoro di ottimizzazione, e piuttosto complesso se stai cercando la soluzione ottimale the . Fortunatamente credo che sia uno di quei casi in cui andrà bene.

La prima cosa da fare è stabilire un criterio di qualità matematico, ovvero una formula che, data una permutazione della lista, restituirà un singolo numero che descrive quanto sia buona o cattiva tale permutazione.

Un semplice suggerimento di formula, ogni criterio che vorresti prendere in considerazione dovrebbe avere un peso, dare un peso elevato a criteri importanti e un peso basso ai criteri in cui molte canzoni condividono la stessa proprietà, in modo che quelle non dominare:

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

Più basso è il valore di questa procedura, migliore è la permutazione della lista.

Esecuzione della permutazione

Ora potresti prendere questa formula per math.stackexchange e farti dire quanto sia follemente difficile e possibilmente impossibile trovare la soluzione ottimale per qualsiasi cosa tranne un numero insignificante di canzoni, o potresti semplicemente lanciarle cicli di clock e ottieni una buona soluzione.

Ci sono molti modi per farlo, eccone uno:

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

Questo è un algoritmo un po 'dispendioso, ma è facile da implementare e può gestire tutti i criteri che desideri.

Ottimizzazioni

È possibile applicare diversi ritocchi e ottimizzazioni, eccone alcuni:

Nel calcolo del valore di qualità, non preoccuparti di controllare una canzone contro ogni altra canzone della lista, invece basta controllarla contro le circa 100 canzoni più vicine. Per valori comuni questa ottimizzazione della velocità non ha praticamente alcuna influenza sulla qualità del risultato.

Per un valore raro di una determinata proprietà può essere più efficiente tenere traccia delle istanze esistenti di quel valore piuttosto che cercarle.

Se ritieni che sia importante che i valori con poche istanze siano distanziati in modo uniforme, piuttosto che molto distanti, è probabilmente necessario aumentare il peso per quei valori specifici, ma non per altri valori di quel criterio.

Una funzione pseudo-casuale che seleziona tutte le coppie possibili dalla lista in una distribuzione equa può avere un rendimento leggermente migliore per ogni prelievo rispetto a una scelta casuale normale.

È interessante ciò che i diversi approcci adottano. Farei quanto segue:

Sulla base di tutti i brani riprodotti finora, dai a ciascuno un punteggio. Gioca la traccia con il punteggio più basso (o, nel caso di punteggi identici, uno casuale corrispondente al punteggio più basso). Ripeti.

La parte difficile, ovviamente, è dare un punteggio. Per ogni traccia possibile che potresti suonare in seguito, dovresti passare attraverso ciascuno (o un numero limitato di) tracce che hai già suonato. Se la traccia [possibile successiva] e la traccia [riprodotta di recente] hanno qualcosa in comune, si aggiunge alla partitura, a seconda di quanto hanno in comune, cosa hanno in comune e quanto tempo fa la traccia [riprodotta di recente] era giocato. Probabilmente vorrai che "niente in comune" sia 0, quindi puoi iniziare con tutte le tracce come 0.

Probabilmente vorrai sperimentare alcune playlist fatte a mano per cominciare, per ottenere i giusti calcoli - vuoi il numero di parole in comune, o il quadrato del numero di parole in comune, o la radice quadrata del numero di parole in comune? Esegui tutta la playlist, vedi quali sono in cima alla classifica come "più in comune" e modifica i fattori per ottenere il giusto equilibrio. Forse vuoi andare per lettera, quindi "Duke Ellington" ha un punteggio elevato rispetto a "Duke Elington", ma un punteggio ancora più alto rispetto a "King Elle Duton" (se non ho perso nessuna lettera :) . Dovresti considerare molto attentamente quali campi vuoi confrontare e se vuoi confrontare i campi. Potresti anche considerare i bigram (coppie di lettere, nel caso di Duke ellington, "Du", "uk", "ke", "ee" e così via.

Tieni presente che, se hai un artista molto particolare, quell'artista potrebbe essere ignorato in priorità: potresti sentire una traccia di un artista unico 5 volte, prima di sentire tutte e 10 le tracce di Duke Ellington. Questo potrebbe o potrebbe non essere quello che vuoi. Puoi evitarlo impostando un dizionario di tutto ciò che devi confrontare e con quale frequenza si verificano, quindi se hai molte tracce di Duke Ellington, due tracce di Duke Ellington sono "meno simili" di due di Billy Joe Shaver .

Potrebbe anche valere la pena pre-cacolare un tavolo con ogni combinazione di due coppie di canzoni. Inoltre, quando si considera quale canzone suonare successivamente, è sufficiente ricordare la canzone migliore finora; se il prossimo da considerare ha un punteggio peggiore rispetto alla migliore canzone fino ad ora, puoi saltare a quella successiva.