How to implement a repeating shuffle that's random - but not too random

Question

I've got a list of n 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:

1. once an item has been picked, it shouldn't turn up again in the next few items (say in the next m items, with m obviously strictly < n)
2. you shouldn't have to wait too long for any item to appear - items should appear on average once every n picks
3. the sequence should be non-cyclical

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.

Those constraints eliminate two obvious solutions from contention:

• We can't simply pick rnd(n) 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.
• 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 2n - 1 picks, it doesn't completely prevent an item repeating.

A naive solution might be to pick at random but reject picks if they occurred in the last m picks; that means keeping a list of m 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..

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 (m items) I shuffle it, and move it to the bottom of the draw pile.

This meets the requirement, but that shuffle once every m 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.

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.

Answer 1

To generate your list do the following. Have a draw and discard pile. Initially the discard pile is empty. Pick your first item at random from the draw pile. Add it to the play list and then put it in the discard pile. When there are m items in the discard pile, take the last item (least recently used) from the discard pile and add it to the draw pile. The playlist will be random, but without shuffle required.

Here it is in ruby:

SONGS = [ "Pink Floyd - Wish You Were Here",
          "Radiohead - Bones",
          "Led Zeppelin - Black Dog",
          "The Cure - A Strange Day",
          "Massive Attack - Teardrop",
          "Depeche Mode - Enjoy the Silence",
          "Wilco - Jesus etc." ]

DONT_REPEAT_FOR = 3

def next_item pick, discard
  result = pick.delete_at(rand(pick.count));
  discard.push result
  pick.push(discard.shift) if (discard.count > DONT_REPEAT_FOR)
  result
end

def playlist_of_length n
    discard = []
    pick = SONGS
    playlist = []
    (0..n).each { playlist.push next_item(pick, discard) }
    playlist
end

EDIT: Added playlist_of_length method to make it clearer how you call next_item to generate the playlist

Answer 2

Aside queue algorithm implemententation and visual verification

In Mathematica:

Play[themes_, minCycle_, iterations_] :=
 Module[{l, queue, played},
  l = Range[themes]; 
  queue = {};
  played = {}; (*just for accounting*)

  While [  Length@played < iterations,
   (AppendTo[queue, #]; l = DeleteCases[l, #]) &@RandomChoice[l];
   If[Length[queue] > minCycle, (AppendTo[l, First@queue]; queue = Rest@queue)];
   AppendTo[played, Last@queue]
   ];
  Return[played];
  ]

MatrixPlot[Partition[Play[100, 50, 20000], 100], ColorFunction -> Hue]

Let's see that there are not obvious repetitive patterns:

Comparing different cycles lengths: