4 ms·

> The randomizer stores a single vector containing all the items of the playlist. This vector is not shuffled at once. Instead, steps of the Fisher-Yates algori

> The randomizer stores a single vector containing all the items of the playlist. This vector is not shuffled at once. Instead, steps of the Fisher-Yates algorithm are executed one-by-one on demand. Fisher-Yates is the generalization of what is known as the "7-bag randomizer" in the Tetris community (same problem: you want to distribute 7 pieces randomly but want to avoid repetition). It's funny how what you think as inconsequential trivia about your niche hobby can turn out in unexpected places !

rom1v 7y ago
Interesting, I didn't know about the tetris randomizers! https://simon.lc/the-history-of-tetris-randomizers https://simon.lc/the-history-of-tetris-randomizers
- jchw 7y ago
  This article, while a nice summary, does miss some details that are quite important. TGM in particular uses Mersenne Twister as its PRNG, whereas NES Tetris probably uses a linear congruential generator (as was common for many games on 8-bit game consoles to the best of my knowledge.) MT behaves dramatically differently than LCG, and while it may seem like a minor detail, actually feels quite different to play from Math.random implementations I've tried, even when using the same TGM algorithm.
  - xxs 7y ago
    flip note: I dunno which 'Math.random' you mean, the Java version should not be used for anything meaningful (perf. related) as it is a shared 'java.util.Random' that exhibits a contention point, albeit a CAS (not synchronized) but a contention point nonetheless. Also generating a double (from 2 ints) to be converted to an int is a bad idea. Should be just 'random.nextInt(7)'
    - jchw 7y ago
      In particular I’m thinking of JavaScript, but the same thing could be said about libc random. In at least a few puzzle games, the PRNG used has noticeable side effects.
      - xxs 7y ago
        The main issue would be naively using mod to obtain a number in range of (0-n].
        jchw 7y ago
        I understand the issue with modulo bias, but there's plenty of techniques for dealing with that issue. (Not to say that people always do, even in real-world code, but oh well.)
        rom1v 7y ago
        TBH, I think this is acceptable for a playlist random order, even if it's not perfectly evenly distributed.
  - vanderZwan 7y ago
    Wonder how PCG compares then[0]. Maybe it helps to think of these randomizers as noise generators, and then try to figure out what the ideal noise "color" for fun play would be? I guess blue noise for example would be like too predictable random bag generators. [0] http://www.pcg-random.org/ http://www.pcg-random.org/
jchw 7y ago
Incidentally, my loud opinions about guideline Tetris aside, this actually helps me understand this a lot better.
Normal_gaussian 7y ago
Fisher-Yates was one of the first algorithms my CS course exposed me to; nicknamed the knuth shuffle, not 100% why but it is in TAOCP. I implement it relatively frequently (~once a year) as it is often quicker to write than find an implementation. Surveying some peers I was very surprised to find they weren't aware of it!
- xxs 7y ago
  Also known as card deck shuffle, but indeed I have always known it as Knuth. As for peers part, perhaps they use a library function - Java has java.util.Collections.shuffle. OTOH is a single line, provided the generator can produce a random number [0-n).
- vanderZwan 7y ago
  IIRC, Knuth made it famous (because TAOCP). Often with the naming of these things there is a misalignment with who discovered/published it first and who popularized it first. (I personally think naming the algorithm after both is a good compromise)
vanderZwan 7y ago
Looks like he reinvented shuffle vectors on his own. I think a lot of people have over the years, but crazy enough nobody bothered to publish it until February this year! Maybe it felt too intuitive? [0] https://observablehq.com/@jobleonard/shuffle-vectors https://observablehq.com/@jobleonard/shuffle-vectors [1] https://arxiv.org/abs/1902.04738 https://arxiv.org/abs/1902.04738
- rom1v 7y ago
  Shuffling a vector at once is "trivial": https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T... I am not sure to understand what to look in the first link, nor the connection with the second link.
  - vanderZwan 7y ago
    That the shuffle vector is a data structure that shuffles upon push/pop while still maintaining O(1): > From a CompSci angle: this is a data-structure with a built-in Fisher-Yates shuffle. Big-O is the same when you want to shuffle a whole array of n elements at once, namely O(n). The difference is that instead of initiating the vector, then shuffling the whole thing, the shuffling is applied "lazily" as you add elements to it. > This may have benefits in some situations: if you have a "random bag" where you often add a few elements at a time, then want to pick elements at random. One very naive way to do it would be to shuffle the bag every time you pick an element, which as mentioned is O(n). Using a shuffle vector, you can add elements by push, and grab a random element with pop. Since one swap per insertion is enough, picking a random item from our bag is O(1) instead. It looks like your approach has a lot of overlap with this data structure (which specializations specific to your use-case). The data structure is explained in the first link, and was (officially) introduced to CompSci (as in, described in an academic publication) in the paper in the second link. However, in all likelihood a lot of people came up with this approach over the years. For example, when I first shared the notebook in the first link on Twitter, a few game devs came forward saying they implemented something similar for their games before. So I'm just connecting your approach to the wider context of what others have done in this space
sorenjan 7y ago
Spotify has a nice blog post about shuffling music. Not the exact same thing, but interesting nonetheless. https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/ https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/

rom1v 7y ago

Interesting, I didn't know about the tetris randomizers! https://simon.lc/the-history-of-tetris-randomizers https://simon.lc/the-history-of-tetris-randomizers

jchw 7y ago
This article, while a nice summary, does miss some details that are quite important. TGM in particular uses Mersenne Twister as its PRNG, whereas NES Tetris probably uses a linear congruential generator (as was common for many games on 8-bit game consoles to the best of my knowledge.) MT behaves dramatically differently than LCG, and while it may seem like a minor detail, actually feels quite different to play from Math.random implementations I've tried, even when using the same TGM algorithm.
- xxs 7y ago
  flip note: I dunno which 'Math.random' you mean, the Java version should not be used for anything meaningful (perf. related) as it is a shared 'java.util.Random' that exhibits a contention point, albeit a CAS (not synchronized) but a contention point nonetheless. Also generating a double (from 2 ints) to be converted to an int is a bad idea. Should be just 'random.nextInt(7)'
  - jchw 7y ago
    In particular I’m thinking of JavaScript, but the same thing could be said about libc random. In at least a few puzzle games, the PRNG used has noticeable side effects.
    - xxs 7y ago
      The main issue would be naively using mod to obtain a number in range of (0-n].
      - jchw 7y ago
        I understand the issue with modulo bias, but there's plenty of techniques for dealing with that issue. (Not to say that people always do, even in real-world code, but oh well.)
      - rom1v 7y ago
        TBH, I think this is acceptable for a playlist random order, even if it's not perfectly evenly distributed.
- vanderZwan 7y ago
  Wonder how PCG compares then[0]. Maybe it helps to think of these randomizers as noise generators, and then try to figure out what the ideal noise "color" for fun play would be? I guess blue noise for example would be like too predictable random bag generators. [0] http://www.pcg-random.org/ http://www.pcg-random.org/

jchw 7y ago

Incidentally, my loud opinions about guideline Tetris aside, this actually helps me understand this a lot better.

Normal_gaussian 7y ago

Fisher-Yates was one of the first algorithms my CS course exposed me to; nicknamed the knuth shuffle, not 100% why but it is in TAOCP. I implement it relatively frequently (~once a year) as it is often quicker to write than find an implementation. Surveying some peers I was very surprised to find they weren't aware of it!

xxs 7y ago
Also known as card deck shuffle, but indeed I have always known it as Knuth. As for peers part, perhaps they use a library function - Java has java.util.Collections.shuffle. OTOH is a single line, provided the generator can produce a random number [0-n).
vanderZwan 7y ago
IIRC, Knuth made it famous (because TAOCP). Often with the naming of these things there is a misalignment with who discovered/published it first and who popularized it first. (I personally think naming the algorithm after both is a good compromise)

vanderZwan 7y ago

Looks like he reinvented shuffle vectors on his own. I think a lot of people have over the years, but crazy enough nobody bothered to publish it until February this year! Maybe it felt too intuitive? [0] https://observablehq.com/@jobleonard/shuffle-vectors https://observablehq.com/@jobleonard/shuffle-vectors [1] https://arxiv.org/abs/1902.04738 https://arxiv.org/abs/1902.04738

rom1v 7y ago
Shuffling a vector at once is "trivial": https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#T... I am not sure to understand what to look in the first link, nor the connection with the second link.
- vanderZwan 7y ago
  That the shuffle vector is a data structure that shuffles upon push/pop while still maintaining O(1): > From a CompSci angle: this is a data-structure with a built-in Fisher-Yates shuffle. Big-O is the same when you want to shuffle a whole array of n elements at once, namely O(n). The difference is that instead of initiating the vector, then shuffling the whole thing, the shuffling is applied "lazily" as you add elements to it. > This may have benefits in some situations: if you have a "random bag" where you often add a few elements at a time, then want to pick elements at random. One very naive way to do it would be to shuffle the bag every time you pick an element, which as mentioned is O(n). Using a shuffle vector, you can add elements by push, and grab a random element with pop. Since one swap per insertion is enough, picking a random item from our bag is O(1) instead. It looks like your approach has a lot of overlap with this data structure (which specializations specific to your use-case). The data structure is explained in the first link, and was (officially) introduced to CompSci (as in, described in an academic publication) in the paper in the second link. However, in all likelihood a lot of people came up with this approach over the years. For example, when I first shared the notebook in the first link on Twitter, a few game devs came forward saying they implemented something similar for their games before. So I'm just connecting your approach to the wider context of what others have done in this space

sorenjan 7y ago

Spotify has a nice blog post about shuffling music. Not the exact same thing, but interesting nonetheless. https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/ https://labs.spotify.com/2014/02/28/how-to-shuffle-songs/