Shuffle Groups algorithm

Question

I need a "shuffle albums" algorithm for my audio player like in foobar2k. So the problem is: I have a list of tracks, sorted according to some criteria so that tracks with same album are all adjacent. Now I need to be able to play songs from the playlist in "shuffle albums" mode, that is, if the next track is from the same album, just play it, otherwise, go to the first track of a next random album. If the user wants to play previous track, do the same thing but backwards. So the question is: how do I know what previous album was? I really don't want to keep a history of played albums, or keep a separate list.

Currently, I implement regular shuffle mode by giving each track random shuffle index, so that I can find previous and next tracks by finding tracks with largest shuffle index smaller than current and smallest shuffle index larger than current. But it doesn't work for shuffle albums mode. Can somebody help me with this?

Sample input:

Track 1, Album A
Track 2, Album A
Track 1, Album B
Track 2, Album B
Track 3, Album B
Track 1, Album C
Track 2, Album C
Track 3, Album C

Let's say current track is Track 1, Album A. Next track will be Track 2, Album A. Next track is not from the same album, so a first track from a random album should be chosen, let's say, Track 1, Album C. What I'm doing now is choosing next track as if it was regular shuffle mode, then going to the first track of its album, thus loosing information from where I came to this album. SO when the user wants to go to the previous album, I have no information how I got there. Hope that makes the question clearer.

Thank you.

Answer 1

You can reuse your shuffle index technique to index albums. Now a track index is an (album shuffle index, track pos) pair. To navigate, increment / decrement the track pos; if it goes out of bounds, update the album index.

That said, you should reconsider not keeping an history; it would let you skip back much faster with a large number of albums.