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

Ah ok, thank you for the details!

In that case, indeed there is some overlap (when removing an item, the randomizer only swaps 2 items in the "non-ordered" part).