Ah, the old “should a random shuffle repeat songs” debate. Haven’t thought about that in years.
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.
> 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.
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.
Thanks!! I've been looking for an algo to draw pixel positions in a pseudorandom way only once. I didn't know a way to do it without storing and shuffling all positions. Now, I only need to draw a centered filled circle, so there might be a prime number for it, and even if the prime only does it for a given amount of points, I could switch to other primes until the circle is filled, and get an optimal and compressed single-visit scattering algo.
You may have mathed over my head, but I’m not seeing how it avoids playing already-played songs when the list is expanded.
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)?
> 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.
One way to do it without retaining additional state would be to generate the initial shuffle for N > current song list. If the new songs' indices come up, they get played. You skip any indices that don't correspond to a valid song when it's time to play them.
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.
Eh, it depends what you mean by "works". If you mean that if you add new songs in the middle of playback, it doesn't guarantee that every song is played exactly once before any are repeated, sure, but you can't really do that unless you're actually tracking all of the songs.
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.
I’d suggest the general solution: the machine can keep a list of the songs it has played, and bump the oldest entries off the list. The list length can be user configurable, 0 handles your truly random friend, 1 would be enough to just avoid immediate repeats, or it could be set to the size of the library. 100 could, I think, give you enough time to not notice any repeats I think, right?
I'm comfortable with "random play" meaning we're going to pick at random each time but I'm not OK with the idea that's "shuffle" shuffle means there were a list of things and we shuffled it. Rolling a D20 is random but it's not shuffling. Games with a random element deliberately (if they're well designed) choose whether to have this independence or not in their design.
A shuffle is type of permutation. There is room to disagree on the constraints on the type of permutations allowed and how they are made. Nevertheless, I 100% agree that sampling with replacement is not a shuffle.
While I agree with you, as soon as the semantics of “random” vs “shuffle” enter the conversation, lay people are lost.
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.
If you let programmers do randomness you're in a world of pain.
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.
My favorite example of RNG misuse resulting in sampling bias is the general approach that looks like `arr.sort(() => Math.random() - 0.5)`.
> 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.
Wow, that's an abusive ordering function. Presumably this is a thing people might write in... Javascript? And I'm guessing Javascript has to put up with them doing this and they get a coherent result, maybe it's even shuffled, because eh, it worked in one browser so we're stuck with it.
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.
You must track the permutation you're stepping through.
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.
I'm really enjoying the discussion on how shuffle means different things to different people (I personally prefer random, but implementing `shuffle` specifically sounds fun with all of this)
> 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 think all of this depends on the UI presentation, but when “shuffle” is used, I think a good starting point is “what would a person expect from a deck of cards”, since that’s where the metaphor started.
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.
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.