Este es un trabajo de optimización y bastante complejo si está buscando la solución óptima. Afortunadamente, creo que es uno de esos casos donde lo suficientemente bueno será suficiente.
Lo primero que debe hacer es establecer un criterio matemático de calidad, es decir, una fórmula que, dada una permutación de la lista, devolverá un solo número que describe cuán buena o mala es esa permutación.
Una sugerencia de fórmula simple, cada criterio que le gustaría tener en cuenta debe tener un peso, dar un alto peso a los criterios importantes y un bajo peso a los criterios en los que muchas canciones comparten la misma propiedad, para que esas no dominen :
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] )
Cuanto menor sea el valor que produce este procedimiento, mejor será la permutación de la lista.
Haciendo la permutación
Ahora podría llevar esta fórmula a math.stackexchange y hacer que le digan cuán increíblemente difícil y posiblemente prácticamente imposible es encontrar la solución óptima para cualquier cosa que no sea un número trivial de canciones, o simplemente puede lanzarle ciclos de reloj y obtener un buena solución.
Hay muchas formas de hacerlo, aquí hay una:
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
Este es un algoritmo algo derrochador, pero es fácil de implementar y puede manejar tantos criterios como uno desee.
Optimizaciones
Se pueden aplicar cargas de diferentes ajustes y optimizaciones, aquí hay algunos:
En el cálculo del valor de calidad, no se moleste en comparar una canción con cada una de las otras canciones de la lista, en su lugar, simplemente verifíquela con las 100 canciones más cercanas. Para valores comunes, esta optimización de velocidad prácticamente no tiene influencia en la calidad del resultado.
Para un valor raro de una propiedad dada, puede ser más eficiente rastrear las instancias existentes de ese valor que buscarlas.
Si considera que es importante que los valores que tienen pocas instancias estén espaciados de manera pareja, en lugar de estar muy separados, probablemente sea necesario aumentar el peso para esos valores específicos, pero no para otros valores de ese criterio.
Una función pseudoaleatoria que selecciona todos los pares posibles de la lista en igual distribución puede tener una eficiencia ligeramente mejor por selección que una selección aleatoria normal.
while (length(songs) > 0) { x := rand(); addElem(shuffle, songs[x]); remElem(songs, x); }
pero usted dice que quiere un "shuffle definitivo". No sé lo que realmente quieres con eso, incluso leyendo la pregunta ...