[antiterra]

I think the issue was playing the same artist or album back-to-back. So they made ‘smart shuffle’ in 2005. (https://www.wired.com/story/requiem-for-the-ipod-shuffle/)

A shuffle already implies shuffling like a deck of cards, so you wouldn’t get duplicates unless you had two of the same card, and I that’s how it was described in the manual.

[jimbobthrowawy]

Is there any algorithm that would do that without actually storing a list of indices, or track IDs?

I can't think of why someone would prefer a truly random song being played from a playlist rather than the "deck of cards" method.