I'm not sure how common this was: the shuffle function in a CD player I used always used the same order for the same CD. Maybe they had a predefined shuffle-list of integers, that they used mod the number of tracks on the CD. Or seeded their pseudo RNG with something from the CD. Whatever the implementation, you only got two modes for playing one CD: in order, or "shuffle" - in a predefined, seemingly random, but still always consistent order.