pif_ShuffleQueue

pif_ShuffleQueue is a twist on the usual queue data structure. In a standard queue, you pop data from the beginning of the queue and push it onto the end of the queue—that is, it's a FIFO (first in, first out) data structure. This structure, which I call a shuffle queue, switches things up by popping off the front of the queue but pushing only probabilistically to the end of the queue. The algorithm to push data onto the shuffle queue is defined so that the n^th index is n times more likely to be selected as the position to add data than the 1st index. E.g., the 10^th index is 10 times more likely than the first to be added to, the 50^th index is 50 times more likely than the first, and so forth.

The imagined use case for this structure is when one wishes to pick data randomly from some structure, but wants to make repeat picks less likely than usual. It is a common flaw (known as the gambler's fallacy) to assume that because something random happened recently, it is less likely to happen again soon. For example, many think that because you just rolled a 2 on a six-sided dice you're less likely to roll a 2 again—but this is not true! The phrase to keep in mind is "dice don't have memory".

Shuffle queue bridges the gap between the naive expectation of how randomness works and the mathematical reality of the situation. One always selects data from the beginning of the shuffle queue, but because it is inserted with uneven weights some position of the queue it is actually true that recently-selected objects are less likely to be selected than ones that haven't appeared in a while. Frequently, from a game design standpoint this is the preferred situation.

Interoperability

This library is natively interoperable with two of my other libraries, pif_Iterator and pif_Random. When one or both of these libraries is detected, pif_ShuffleQueue will automatically add additional behavior to incorporate their functionality. Take a look at the documentation for more details.

The MIT License

Copyright (c) 2019-2024 Timothy "popisfizzy" Reilly

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to
deal in the Software without restriction, including without limitation the
rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
sell copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
IN THE SOFTWARE.