3 ms·
> 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
by vitus 2y ago
> 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.
- readyplayernull 2y agoThanks!! 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.
- meindnoch 2y agoMind you, placing many pixels at coordinates from a linear congruential generator will not look random at all.
- satvikpendem 2y agoHave you seen this algorithm for dithering? Reminds me of your problem. https://news.ycombinator.com/item?id=42808889 https://news.ycombinator.com/item?id=42808889
- readyplayernull 2y agoYes, but another requirement is the algo to be very fast, and dithering takes way more operations than the proposed Fermat PRNG.
- bazzargh 2y agothis is something you should read https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/ https://extremelearning.com.au/unreasonable-effectiveness-of... (it's effectively the fermat prng described, but goes into more depth)
- brookst 2y agoYou 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)?
- vitus 2y ago> 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.
- Dylan16807 2y ago> 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. You probably shouldn't have quoted "detecting additions and updating the list, etc." then.
- AlotOfReading 2y agoOne 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.
- meindnoch 2y agoThis only works for a fixed list.
- vitus 2y agoEh, 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.