StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POHow to implement a repeating shuffle that's random - but not too random
text
Body
copied!<p>I've got a list of <em>n</em> items. I want an algorithm to let me pick a potentially infinite sequence of items from that collection at random, but with a couple of constraints:</p> <ol> <li>once an item has been picked, it shouldn't turn up again in the next few items (say in the next <em>m</em> items, with <em>m</em> obviously strictly < <em>n</em>)</li> <li>you shouldn't have to wait too long for any item to appear - items should appear on average once every <em>n</em> picks</li> <li>the sequence should be non-cyclical</li> </ol> <p>Basically, I want an algorithm to generate the playlist for an MP3 player with 'shuffle' and 'repeat' turned on, that makes sure it doesn't play the same song too close to itself, and makes sure it plays all your songs evenly, with no discernible pattern.</p> <p>Those constraints eliminate two obvious solutions from contention:</p> <ul> <li>We can't simply pick rnd(<em>n</em>) as the index for the next item, because that will not guarantee no repetition; it may also take a long time to pick some items.</li> <li>We can't just pre-shuffle the list with a Fisher-Yates shuffle, and iterate over it repeatedly, reshuffling it each time we reach the end; while that guarantees items turn up at most after <em>2n - 1</em> picks, it doesn't completely prevent an item repeating. </li> </ul> <p>A naive solution might be to pick at random but reject picks if they occurred in the last <em>m</em> picks; that means keeping a list of <em>m</em> previous picks, and checking each pick against that list every time, which makes the algorithm nondeterministic and slow at the same time - lose-lose. Unless I'm missing something obvious..</p> <p>So I have an algorithm I'm using now which I'm a little dissatisfied with. I've derived it by analogy with a deck of cards, where I have a draw-pile and a discard-pile. I start off with the complete list, shuffled, in the draw pile, the discard pile empty. The next item is read from the top of the draw pile, and then placed in the discard pile. Once the discard pile reaches a certain size (<em>m</em> items) I shuffle it, and move it to the bottom of the draw pile.</p> <p>This meets the requirement, but that shuffle once every <em>m</em> picks bothers me. It's O(1) normally, but O(m) one time in m. That amounts to constant time, on average, but there must be a cleaner solution that shuffles the discards in as it goes.</p> <p>It seems to me that this is such a simple, generic, and common problem, it must have one of those double-barreled algorithms, like Fisher-Yates or Boyer-Moore. But my google-fu is clearly not strong, as I've yet to find the set of terms that locates the inevitable 1973 ACM paper which probably explains exactly how to do this in O(1) time, and why my algorithm is deeply flawed in some way.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload