Good implementations actually don't make a random choice, but do a random sort and then play the whole list, then random sort again, then play again the whole l

Good implementations actually don't make a random choice, but do a random sort and then play the whole list, then random sort again, then play again the whole list, etc. The only possible problem here is when the last song in one playthrough is the same as the first song in the next playthrough. But even that can be overcome by re-random-sorting the follow-up.