I’m with you in that I think shuffle should be a single list of all songs, played in a random order. But that requires maintaining state, detecting additions and updating the list, etc.
Years ago, a friend was adamant that shuffle should mean picking a random song from the list each time, without state, and if that means the same song plays five times in a row, well, that’s what random means.
You should be able to accomplish this with trivial amounts of state (as in, somewhere around 4 ints).
As an example, I'm envisioning something based on Fermat's little theorem -- determine some prime `p` at least as big as the number of songs you have (N), then to determine the next song, use n := a*n mod p for fixed choice of 1 < a < p, repeating as necessary as long as n > N. This should give you a deterministic permutation of the songs. When you get back to the first song you've played, you can choose to pick a new `a` for a new shuffle, or you can just keep that permutation.
If the list of songs changes, pick new a, p, and update n to be the new position of your current song (and update your notion of "first song of this permutation").
(Regarding why this works: you want {a} to be a generator for the multiplicative group formed by Z/pZ.)
Linear congruential generators have terrible properties if you care about the quality of your randomness, but if all you're doing is shuffling what order your songs play in, they're fine.
Say I have a 20 song list, and after listening to 15 I add five more. How does this approach only play the remaining 10 songs (5 that were remaining plus 5 new)?
It doesn't. If you add 5 more songs, then the algorithm as presented will just treat it as if you're starting a new shuffle.
If you genuinely need to keep track of all the songs you've already played and/or the songs that you have yet to play, then I'm not sure you can do much better than keeping a list of the desired play order, randomized via Fisher-Yates shuffle each time you want a new shuffled ordering -- new songs can be appended to said list and shuffled in with the as-yet-unplayed songs.
You probably shouldn't have quoted "detecting additions and updating the list, etc." then.
This has some obvious downsides (e.g. an empty slot that was skipped when played and filled by a later insert won't be played), but it handles both insertion and deletions without replaying songs and you only need to store a single integer.
Many approaches that guarantee that property have pathological behavior if, say, you add a new song to your library after each song that you've played.
To me “shuffle” is a good metaphor because a shuffled deck of cards works a specific way (you’d be very surprised to draw the same card twice in a row!)
But these things are implemented by programmers who sometimes start with implementation (“random”) and work back to user experience. And, for a specific type of technical person, “with replacement” is exactly what they’d expect.
On the whole programmers given a source of random bytes and told to pick any of 227 songs at random using this data will take one byte, compute byte % 227 and then be astonished that now 29 of the songs are twice as likely as the others to be chosen†.
In a class of fifty my guess is you're lucky if one person asks whether the random bytes are cheap (and so they should just throw away any that aren't < 227) showing they know what "random" means and all the rest will at least attempt that naive solution even if some of them try it out and realise it's not good enough.
† As a bonus in some languages expect some solutions to never pick the first song, or never pick the last song.
> you're lucky if one person asks whether the random bytes are cheap (and so they should just throw away any that aren't < 227)
If you can't deal with the 10% overhead from rejection sampling (assuming your random bytes are uniform), I guess you could try mushing that entropy back into the rest of your bytestream, but yuck.
In Rust this abuse would either "work" or panic telling you that er, that's not a coherent ordering so you need to stop doing that. Not certain whether the panic can only arise in debug builds (or whether it would detect this particular abuse, it's not specified whether you will panic only that you might if you don't provide a coherent ordering).
In C++ this is Undefined Behaviour and there's a fair chance you just introduced an RCE vulnerability into your codebase.
https://stackoverflow.com/questions/962802/is-it-correct-to-...
An example of this out in the wild: https://www.robweir.com/blog/2010/02/microsoft-random-browse...
Any info on how can I achieve this
E.g. you have 4 items. You shuffle them to get a random permutation:
4 2 1 3
Note: these are not indices, but identifiers. Let's say you go through the first two items:
4 2 <you're here> 1 3
And two new items arrive. You insert each item into a random position among the remaining items. E.g:
4 2 <you're here> 5 1 6 3
If items are to be deleted, there are two cases: either they have already been visited, in which case there's nothing to do, or they're in the remaining list, in which case you have to delete them from there.
> You insert each item into a random position among the remaining items
Thinking about shuffle + adding, I would have thought "even if it's added to a past position", e.g.
`5 4 6 21 3` as valid.
What do folks expect out of shuffle when it reaches the end? A new shuffle, or repeat with the same permutation?
I don’t think that provides a totally clear answer to “what happens at the end”, but for me it’d lean me towards “a new shuffle”, because for me most of the time a shuffled deck of cards draws its last card, the deck will be shuffled again before drawing new cards.