1. let S = set of songs to be played
2. let N = number of songs
3. repeat until bored:
3.1. let R = set of last [N / 2] songs we played
3.2. pick a song at random from S \ R; play it
You may want to tweak step 3.2 to give higher probabilities of picking songs that haven't been played for longer.
1. let S = set of songs to be played
2. let N = number of songs
3. repeat until bored:
3.1. let R = set of last [N / 2] songs we played
3.2. pick a song at random from S \ R; play it
You may want to tweak step 3.2 to give higher probabilities of picking songs that haven't been played for longer.