I'd like to write an "ultimate shuffle" algorithm to sort my mp3 collection

Question

I'm looking for pseudocode suggestions for sorting my mp3 files in a way that avoids title and artist repetition. I listen to crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. singing old standards. Each artist records many of the same songs - Fly Me To The Moon, The Way You Look Tonight, Stardust etc. My goal is to arrange the songs (or order the playlist) with the maximum space between artists and song titles. So if I have 2000 songs and 20 are by Ella I'd like to hear her only once in every 100 songs. If 10 artists sing Fly Me To The Moon I'd like to hear it once in every 200 songs. Of course I want to combine these two requirements to create my "ultimate shuffle".

I know this is a fairly wide open question. I haven't started programming it yet so I'm just looking for suggestions of a good approach to take. I actually have some other requirements regarding evenly spacing other song attributes but I won't get into that here.

---

As a starting point I'm modifying code I found here to manipulate mp3 files and read ID3 tags.

I wrote a small app that satisfies my need using parsifal's answer below. I also wrote a follow up question here. Thanks for all the great responses!

Answer 1

Do you want to run your program once and generate a playlist, or pick the next song live?

If the latter, then the answer is simple:

• Create an array that contains all of your songs, with artist and title
• Create a list (linked list preferable) to hold recently-played song titles. This list starts out empty, and each time you play a song you add it to the list. When the list hits your desired "no song repeat" size, drop the oldest (first) entry.
• Ditto for a list of artists.

Picking a song then becomes the following sequence of steps:

1. Randomly pick a song from the "all songs" array. This is just a random number between 0 and the size of the array.
2. See if that song is already in the played songs list. If it is, go back to step #1.
3. See if the artist is already in the played artist list. If it is, go back to step #1.
4. Add the song artist/title to the appropriate lists, dropping old entries if needed.
5. Play the song.

There are a couple of possible issues, but they should only matter if you're doing this as homework and not a real project.

• As @Dukeling said in a comment, if your collection is dramatically unbalanced in favor of a single artist or song title, you may get into a loop where you constantly reject songs. In practice, this is not going to be an issue. The solution is that you need to reduce the size of the "already seen" lists. And adding counters at steps #2 and #3 can tell you if it's a problem (if you see 10 failures in a row, raise a warning and/or reduce the size of the list).
• If you're trying to produce a playlist that contains all of your songs played only once, you'll need to remove songs from the source array. This will also change how you deal with too many "recently played" failures (because eventually you might end up with only one artist in your source array).
• If your ID3 tags are anything like mine, they contain plenty of misspellings. Does "Duke Ellington" need to be different from "Duke Elingten"? If yes, then look into using a Levenstein matcher when scanning the "recently played" lists.

Answer 2

I've done something like this before using a generator (in C#, an infinite loop that yields each loop iteration). Each iteration looks at its pool of songs (or whatever) and tosses out ones that have been played too recently (or whatever negative criteria). Then you pick one from the filtered list, and update your state. As your state drifts (you play non-Sinatra songs) the criteria breaks down and your excluded songs start being re-included.

Of course there's corner cases to deal with:

• What happens if you throw out all the songs? (usually just pick one at random, hoping to destabilize the state)
• Should some criteria be preferred? (usually the case, maybe you don't want to play Fly Me to the Moon back to back, and would prefer not to play Sinatra back to back, but if that's all you have...)
• What happens if your collection of songs gets updated mid-fight? (usually easy to deal with, but concurrency might have issues depending on usage)

Answer 3

Ignoring the outliers of your question that Telastyn brings up, it sounds like you have a variation on the knapsack problem. Fortunately, it's a pretty well documented algorithm.

From 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.

There are some potentially relevant variations listed in that article along with an additional list of knapsack problems

---

One variation of the knapsack problem is the multi-objective knapsack problem. The ant colony algorithm is suggested as a means of solving that problem. The ant colony approach might be the easiest way for you to avoid the NP-hard aspects of your question.

I could also see considering your problem as an extreme variant of the traveling salesman problem. Each city to visit is really a song that you want played, but I'm not sure how you would specify the intervals between artists. This suggestion is also related to / can be solved by the ant colony approach.

Answer 4

I am working under the assumption that this is a "here is my library, run this program and generate an order to play the songs in."

This hasn't been implemented and I am uncertain how well it will preform its shuffling. It may be that I am a bit too strict in the filter, which would result (I believe) in a prescribed order for the remainder given an initial set of songs.

One has an ideal_gap hash. This is calculated by the density of a song with a given property (artist, album, title). If one has 2000 songs and 20 of them are by an artist named Ella, the ideal_gap{'artist'}{"ella"} would be 100.

Having this information one also has the max of the ideal_gap values. Lets call this max_gap.

Consider: have a maximum to the ideal_gap value to prevent a song that only two artists have sung from preventing the other song from being played 1000 songs later, and also drastically increasing the max_gap value resulting in many iterations of "back off, no songs, back off, no songs".

Examining the last max_gap songs played (this can be populated from a previous run so that if it finished with Frank Sinatra singing Fly Me To the Moon, the next run won't start with the same song by chance), one filters songs out of the library resulting in a set of candidate songs. A song would only be in the candidate songs if all of its gaps are less than the ideal_gap for those properties.

From the set of candidate songs, select one at random.

Consider: weighting the set so that songs that attributes with a higher max gap are weighted to be more likely. This way, one doesn't have all of the larger max gap songs piling up at the end of the playlist.

Consider: instead of having all three properties being greater than the ideal gap, just two out of three. This may mean that something could be played sooner than the ideal ideal, but increases the size of the candidate song set meaning the "select one at random" has a more options.

If there are no songs that fill the requirements, back off the max_gap by 1, and all ideal_gaps by n/max_gap percent where n is the number of times this has been backed off. This way if there is a max_gap of 100, and it has been backed off 5 times in this iteration, an ideal_gap of 100 would be adjusted to temporarily be 95, and an ideal_gap of 20 would be adjusted to temporarily be 19. Repeat backing off the gap until there is at least one candidate song, and then select it as above.

Consider: have a minimum pool size. This adds to the variance, but may result in having a song played sooner than the ideal gap when there is another song that could be played.

Answer 5

This is an optimization job, and a pretty complex one if you are looking for the optimal solution. Fortunately I believe it to be one of those cases where good enough will do.

First thing to do is to establish a mathematical quality criterion, that is a formula that given a permutation of the list will return a single number describing how good or bad that permutation is.

A simple formula suggestion, each criteria that you would like taken into account should be given a weight, give a high weight to important criteria, and a low weight to criteria where a lot of songs share the same property, so that those do not dominate:

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

The lower a value this procedure produce, the better the list permutation is.

Making the permutation

Now you could take this formula to math.stackexchange and have them tell you how insanely difficult and possibly practically impossible it is to find the optimum solution for anything but a trivial number of songs, or you could just throw clock cycles at it and get a good solution.

There are many ways of doing this, here is one:

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

This is a somewhat wasteful algorithm, but it is easy to implement and can deal with as many criteria as one desire.

Optimizations

Loads of different tweaks and optimizations can be applied, here are a few:

In quality value calculation, don't bother checking a song against every other song on the list, instead just check it against the 100 or so closest songs. For common values this speed optimization has practically no influence on the quality of the result.

For a rare value of a given property it may be more efficient to track the existing instances of that value than to search for them.

If you feel that it is important that values that have few instances get spaced close to even, rather than just far apart it is probably necessary to increase the weight for those specific values, but not for other values of that criterion.

A pseudo-random function that pick all possible pairs from the list in equal distribution may have a slightly better efficiency per pick than a normal random pick.

Answer 6

It is interesting what different approaches people take. I'd do the following:

Based on all the tracks played so far, give each one a score. Play the track with the lowest score (or, in the case of identical scores, a random one matching the lowest score). Repeat.

The difficult bit, of course, is giving a score. For each possible track you might play next, you would have to go through each (or a limited number of) tracks you have already played. If the [possible next] track and [recently played] track have something in common, you add to the score, depending on how much they have in common, what they have in common, and how long ago the [recently played] track was played. You would probably want "nothing at all in common" to be 0, so you can start off with all tracks as 0.

You will probably want to experiment with some hand-crafted playlists to begin with, to get the maths right - do you want the number of words in common, or the square of the number of words in common, or the square root of the number of words in common? Run your entire playlist through, see which ones float to the top as being "most in common", and hand-tweak the factors to get the balance right. Maybe you want to go per-letter, so "Duke Ellington" has a high score when compared to "Duke Elington", but an even higher score when compared to "King Elle Duton" (if I haven't lost any letters :). You should consider very carefully which fields you want to compare, and if you want to compare between fields. You might even consider bigrams (pairs of letters; in the case of Duke ellington, "Du","uk", "ke", "ee", and so forth.

Note that, if you have a lot of a particular artist, that artist might be dropped down in priority - you might hear a track by a unique artist 5 times, before you hear all 10 of your Duke Ellington tracks. This might or might not be what you want. You could avoid this by setting up a dictionary of everything you have to compare, and how often they occur, so if you have lots of Duke Ellington tracks, two tracks that are by Duke Ellington are "less similar" than two by Billy Joe Shaver.

It might even be worth pre-caculating a table with every combination of two pairs of songs. Also, when considering which song to play next, you only need to remember the best song so far; if the next one to consider has a worse score than the best song so far, you can skip to the next.