Thats why some players have "random" and "shuffle".

Random is truly random, it might play the same two songs multiple times back to back. Highly unlikely, but it might.

Shuffle has a thing built in that avoids a song if it has been played within X amount of time or plays. Some shuffles might have other criteria as well.

The algorithm the grandparent comment suggests is equally random. It's just that it's a random sequence rather than a random selection.

I remember reading this about the iPod, where they programed it to not play the same artist multiple times in a row or within certain number of songs of each other.

Previous comment wants random order not fully random