[masklinn]

> I don't know if this is what iTunes used to do

It is. iTunes would play a song, and randomly select the next one (it would do random play, rather than shuffle).

Nowadays it generates a shuffled playlist and goes along, and people whine because it doesn't reshuffle automatically (you have to disable and enable shuffle to reshuffle).

An other option is to use random sampling, and to re-sample after you're done with the current set (possibly excluding any song of the previous sample)