20

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.

James Hart
  • 1,251
  • 1
  • 9
  • 11
  • @gradbot - That might just be what I'm looking for. I had a feeling there was a solution which worked in place in an array, partitioning the active (shuffled) and inactive (recently picked) items. Now, add it as a new answer and after I've investigated it it may get an accept :) – James Hart Mar 30 '11 at 02:14

4 Answers4

13

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

tonytony
  • 1,994
  • 3
  • 20
  • 27
Dean Povey
  • 9,256
  • 1
  • 41
  • 52
  • This has the possibility that a song may not be played for a long time however unlikely it may be if other songs keep getting inserted before it. – gradbot Mar 29 '11 at 04:03
  • I think you may have misunderstood how the playlist gets generated. I updated the code to make it a bit clearer. The plays should be uniformly distributed, with no songs repeated for at least DONT_REPEAT_FOR songs. – Dean Povey Mar 29 '11 at 04:15
  • What I mean is that there is nothing to stop a song from not being played for a long time. Here I wrote a test. http://www.pastie.org/1730795 You can see with only 7 songs there are cases where a song isn't repeated until 40 other songs are played while testing a playlist of length 30,000. – gradbot Mar 29 '11 at 12:56
  • I like the simplicity of the approach - having a queue of items that are out of rotation - but a couple of things bother me still. One is the fact that items can be left unpicked for a long time, potentially missing the 'on average every n' requirement, though I don't have stats to back that feeling up. The other is more around removing items from the middle of a list, which is potentially going to start to take a long time as the list gets big... – James Hart Mar 29 '11 at 13:35
  • 1
    Yeah, that's randomness for you, it is surprising :-). I modified your code slightly to do a frequency count, and it gives: [4264, 4345, 4276, 4277, 4284, 4317, 4238], which I am going chi-square in my head and say is a uniform distribution :-). If you increase the DONT_REPEAT_FOR length you reduce the probability of long plays until you eventually reach the maximum. – Dean Povey Mar 29 '11 at 14:39
  • @James Hart - You could reduce the liklihood of long repeats by biasing the random number generator. e.g. (0..length).each { |i| candidate = rand length; return candidate if candidate <= i } end – Dean Povey Mar 30 '11 at 09:27
  • @James Hart (cont) - That is an approximately O(n) operation, but you can make it constant time by setting the step size dependent on the length. Because more recent items drift to the front of the queue this increases the liklihood that things will get played if they are not recently played. There maybe a cleverer algebraic way to bias the random value, but I am too lazy to check :-). – Dean Povey Mar 30 '11 at 09:30
  • I actually went with an implementation based on this algorithm, though with some optimizations. Instead of a separate queue and list, I managed the items in a single list, treating part of the list (indexes < m) as the discard pile, and part (i >= m) as the draw pile. Moving items to and from the draw pile are just swaps. A cursor moving through the draw pile indexes mimics the queue behaviour. – James Hart Apr 01 '11 at 19:05
  • Maybe implement a weighted random selection with a priority-queue-like data structure? That way items recently back in the rotation are still less likely than items that have never been picked... – sehrgut Feb 25 '18 at 19:05
9

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:

enter image description here

Comparing different cycles lengths:

enter image description here

Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
  • I'm interested to see a graphic for max cycle. :) – gradbot Mar 29 '11 at 13:05
  • I'm not deeply familiar with mathematica syntax, but this looks like a similar algorithm to Dean Povey's - is that correct? – James Hart Mar 29 '11 at 13:44
  • Also, is 'aside queue' the term-of-art for this? Googling reveals most usage of that form is in the context of a 'set-aside queue' in congestion management... – James Hart Mar 29 '11 at 14:12
  • @James My command of the English language is surely not the best. Feel free to edit any misspelling. – Dr. belisarius Mar 29 '11 at 15:32
  • @James Regarding the similarity with the Ruby answer (Dean's), I'm not sure, but that is probably because I can't read Ruby :(. Anyway I was more interested in looking at the resulting patterns that in designing the algorithm. – Dr. belisarius Mar 29 '11 at 15:42
  • @belisarius I wasn't commenting on your use of English, which is fine :) - was just wondering if the term 'aside-queue' was one you'd come across to describe this particular approach before, or just something you made up yourself. Solving the algorithm problem is only the first stage - the hard part, as always, is figuring out what to name the method/class that implements it :) – James Hart Mar 29 '11 at 15:43
  • @James It's just a literal translation from my mother tongue. Take a look at the updated image :) – Dr. belisarius Mar 29 '11 at 15:48
6

After playing a given song, use a pseudo-append to place it near the end of the list. You'll probably want about 1/2 to 2/3 to be truly appended and the other 1/3 to 1/2 spread within the last 5 or so items in the list.

Obviously this won't work for very short lists, but should be fine for lists of 10 or more.

Edit (provide more detail about 'PseudoAppend'):

The following pseudo-code uses a mix of language constructs but should be easy enough to turn into real code.

Given List[songs]

While(PLAY)
    Play(List[0])
    PseudoAppend(List[], 0)

def PseudoAppend(List[], index)
    # test to verify length of list, valid index, etc.
    song = List[index].delete    # < not safe
    List.append(song)
    target = -1

    While( (random() < (1/3)) && (target > -3) )
        Swap(List[target], List[target-1])
        target -= 1

Removing the just-completed song from the list without first having a backup list can result in information loss, but this is just pseudo-code meant to convey an idea.

As you can see, 2/3 of the time the song that was just played will be moved to the back of the list, and 1/3 of the time it will be moved ahead of the last song.

Of the 1/3 chance that the song is moved forward, 2/3 of the time it will only be moved ahead of one song, and the other 1/3 of the time it will be moved ahead of two or more songs. Chance that song moves to last position=66%, second to last position=22%, third to last=12%.

The actual behavior of the PseudoAppend is all governed within the condition of the While statement. You can change the value to compare against the random number generator to make it more or less likely that a song is moved ahead of others, and you can change the value compared to target to adjust how far the just-completed song can move ahead in the list.

Edit II (Python 3 code and sample output for a list of 11 items) 
songlist=[0,1,2,3,4,5,6,7,8,9,10]

import random

def pseudoappend(locallist, index):
    song=locallist[index]
    del(locallist[index])
    locallist.append(song)
    target=-1
    while (random.randint(1,3)==1) and (target> -3):
        locallist[target],locallist[target-1] = locallist[target-1],locallist[target]
        target-=1

for x in range(len(songlist)*9):
    print("%3d" % x, ': ', "%2d" % songlist[0], ': ', songlist)
    pseudoappend(songlist, 0)

print( 'end : ', "%2d" % songlist[0], ': ', songlist)

Here's a sample output running through the list ~9 times. The first column is simply a running index, the second column shows the currently selected song, and the third column shows the current order of the list:

>>> ================================ RESTART ================================
>>> 
  0 :   0 :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
  1 :   1 :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
  2 :   2 :  [2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1]
  3 :   3 :  [3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 2]
  4 :   4 :  [4, 5, 6, 7, 8, 9, 10, 0, 1, 2, 3]
  5 :   5 :  [5, 6, 7, 8, 9, 10, 0, 1, 2, 3, 4]
  6 :   6 :  [6, 7, 8, 9, 10, 0, 1, 2, 3, 4, 5]
  7 :   7 :  [7, 8, 9, 10, 0, 1, 2, 3, 4, 5, 6]
  8 :   8 :  [8, 9, 10, 0, 1, 2, 3, 4, 5, 6, 7]
  9 :   9 :  [9, 10, 0, 1, 2, 3, 4, 5, 6, 7, 8]
 10 :  10 :  [10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 11 :   0 :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
 12 :   1 :  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0]
 13 :   2 :  [2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 0]
 14 :   3 :  [3, 4, 5, 6, 7, 8, 9, 10, 1, 0, 2]
 15 :   4 :  [4, 5, 6, 7, 8, 9, 10, 1, 0, 2, 3]
 16 :   5 :  [5, 6, 7, 8, 9, 10, 1, 0, 2, 3, 4]
 17 :   6 :  [6, 7, 8, 9, 10, 1, 0, 2, 3, 4, 5]
 18 :   7 :  [7, 8, 9, 10, 1, 0, 2, 3, 4, 6, 5]
 19 :   8 :  [8, 9, 10, 1, 0, 2, 3, 4, 6, 7, 5]
 20 :   9 :  [9, 10, 1, 0, 2, 3, 4, 6, 7, 5, 8]
 21 :  10 :  [10, 1, 0, 2, 3, 4, 6, 7, 5, 8, 9]
 22 :   1 :  [1, 0, 2, 3, 4, 6, 7, 5, 10, 8, 9]
 23 :   0 :  [0, 2, 3, 4, 6, 7, 5, 10, 8, 9, 1]
 24 :   2 :  [2, 3, 4, 6, 7, 5, 10, 8, 9, 1, 0]
 25 :   3 :  [3, 4, 6, 7, 5, 10, 8, 9, 2, 1, 0]
 26 :   4 :  [4, 6, 7, 5, 10, 8, 9, 2, 1, 0, 3]
 27 :   6 :  [6, 7, 5, 10, 8, 9, 2, 1, 0, 3, 4]
 28 :   7 :  [7, 5, 10, 8, 9, 2, 1, 0, 3, 4, 6]
 29 :   5 :  [5, 10, 8, 9, 2, 1, 0, 3, 4, 6, 7]
 30 :  10 :  [10, 8, 9, 2, 1, 0, 3, 4, 5, 6, 7]
 31 :   8 :  [8, 9, 2, 1, 0, 3, 4, 5, 10, 6, 7]
 32 :   9 :  [9, 2, 1, 0, 3, 4, 5, 10, 6, 7, 8]
 33 :   2 :  [2, 1, 0, 3, 4, 5, 10, 6, 7, 9, 8]
 34 :   1 :  [1, 0, 3, 4, 5, 10, 6, 7, 9, 8, 2]
 35 :   0 :  [0, 3, 4, 5, 10, 6, 7, 9, 8, 2, 1]
 36 :   3 :  [3, 4, 5, 10, 6, 7, 9, 8, 2, 1, 0]
 37 :   4 :  [4, 5, 10, 6, 7, 9, 8, 2, 1, 0, 3]
 38 :   5 :  [5, 10, 6, 7, 9, 8, 2, 1, 0, 3, 4]
 39 :  10 :  [10, 6, 7, 9, 8, 2, 1, 0, 3, 4, 5]
 40 :   6 :  [6, 7, 9, 8, 2, 1, 0, 3, 4, 5, 10]
 41 :   7 :  [7, 9, 8, 2, 1, 0, 3, 4, 5, 10, 6]
 42 :   9 :  [9, 8, 2, 1, 0, 3, 4, 5, 7, 10, 6]
 43 :   8 :  [8, 2, 1, 0, 3, 4, 5, 7, 10, 6, 9]
 44 :   2 :  [2, 1, 0, 3, 4, 5, 7, 10, 6, 9, 8]
 45 :   1 :  [1, 0, 3, 4, 5, 7, 10, 6, 2, 9, 8]
 46 :   0 :  [0, 3, 4, 5, 7, 10, 6, 2, 9, 8, 1]
 47 :   3 :  [3, 4, 5, 7, 10, 6, 2, 9, 8, 1, 0]
 48 :   4 :  [4, 5, 7, 10, 6, 2, 9, 8, 1, 3, 0]
 49 :   5 :  [5, 7, 10, 6, 2, 9, 8, 1, 3, 0, 4]
 50 :   7 :  [7, 10, 6, 2, 9, 8, 1, 3, 5, 0, 4]
 51 :  10 :  [10, 6, 2, 9, 8, 1, 3, 5, 0, 7, 4]
 52 :   6 :  [6, 2, 9, 8, 1, 3, 5, 0, 7, 4, 10]
 53 :   2 :  [2, 9, 8, 1, 3, 5, 0, 7, 6, 4, 10]
 54 :   9 :  [9, 8, 1, 3, 5, 0, 7, 6, 4, 10, 2]
 55 :   8 :  [8, 1, 3, 5, 0, 7, 6, 4, 10, 2, 9]
 56 :   1 :  [1, 3, 5, 0, 7, 6, 4, 10, 2, 9, 8]
 57 :   3 :  [3, 5, 0, 7, 6, 4, 10, 2, 9, 1, 8]
 58 :   5 :  [5, 0, 7, 6, 4, 10, 2, 9, 3, 1, 8]
 59 :   0 :  [0, 7, 6, 4, 10, 2, 9, 3, 1, 8, 5]
 60 :   7 :  [7, 6, 4, 10, 2, 9, 3, 1, 8, 5, 0]
 61 :   6 :  [6, 4, 10, 2, 9, 3, 1, 8, 5, 0, 7]
 62 :   4 :  [4, 10, 2, 9, 3, 1, 8, 5, 0, 7, 6]
 63 :  10 :  [10, 2, 9, 3, 1, 8, 5, 0, 7, 6, 4]
 64 :   2 :  [2, 9, 3, 1, 8, 5, 0, 7, 6, 4, 10]
 65 :   9 :  [9, 3, 1, 8, 5, 0, 7, 6, 4, 10, 2]
 66 :   3 :  [3, 1, 8, 5, 0, 7, 6, 4, 10, 2, 9]
 67 :   1 :  [1, 8, 5, 0, 7, 6, 4, 10, 2, 9, 3]
 68 :   8 :  [8, 5, 0, 7, 6, 4, 10, 2, 9, 3, 1]
 69 :   5 :  [5, 0, 7, 6, 4, 10, 2, 9, 8, 3, 1]
 70 :   0 :  [0, 7, 6, 4, 10, 2, 9, 8, 3, 1, 5]
 71 :   7 :  [7, 6, 4, 10, 2, 9, 8, 3, 0, 1, 5]
 72 :   6 :  [6, 4, 10, 2, 9, 8, 3, 0, 1, 5, 7]
 73 :   4 :  [4, 10, 2, 9, 8, 3, 0, 1, 5, 7, 6]
 74 :  10 :  [10, 2, 9, 8, 3, 0, 1, 5, 7, 6, 4]
 75 :   2 :  [2, 9, 8, 3, 0, 1, 5, 7, 6, 4, 10]
 76 :   9 :  [9, 8, 3, 0, 1, 5, 7, 6, 4, 10, 2]
 77 :   8 :  [8, 3, 0, 1, 5, 7, 6, 4, 10, 2, 9]
 78 :   3 :  [3, 0, 1, 5, 7, 6, 4, 10, 2, 9, 8]
 79 :   0 :  [0, 1, 5, 7, 6, 4, 10, 2, 3, 9, 8]
 80 :   1 :  [1, 5, 7, 6, 4, 10, 2, 3, 9, 8, 0]
 81 :   5 :  [5, 7, 6, 4, 10, 2, 3, 9, 8, 1, 0]
 82 :   7 :  [7, 6, 4, 10, 2, 3, 9, 8, 1, 0, 5]
 83 :   6 :  [6, 4, 10, 2, 3, 9, 8, 1, 0, 7, 5]
 84 :   4 :  [4, 10, 2, 3, 9, 8, 1, 0, 7, 5, 6]
 85 :  10 :  [10, 2, 3, 9, 8, 1, 0, 7, 5, 6, 4]
 86 :   2 :  [2, 3, 9, 8, 1, 0, 7, 5, 6, 4, 10]
 87 :   3 :  [3, 9, 8, 1, 0, 7, 5, 6, 4, 2, 10]
 88 :   9 :  [9, 8, 1, 0, 7, 5, 6, 4, 2, 10, 3]
 89 :   8 :  [8, 1, 0, 7, 5, 6, 4, 2, 10, 3, 9]
 90 :   1 :  [1, 0, 7, 5, 6, 4, 2, 10, 8, 3, 9]
 91 :   0 :  [0, 7, 5, 6, 4, 2, 10, 8, 3, 1, 9]
 92 :   7 :  [7, 5, 6, 4, 2, 10, 8, 3, 1, 9, 0]
 93 :   5 :  [5, 6, 4, 2, 10, 8, 3, 1, 9, 0, 7]
 94 :   6 :  [6, 4, 2, 10, 8, 3, 1, 9, 0, 7, 5]
 95 :   4 :  [4, 2, 10, 8, 3, 1, 9, 0, 7, 6, 5]
 96 :   2 :  [2, 10, 8, 3, 1, 9, 0, 7, 6, 4, 5]
 97 :  10 :  [10, 8, 3, 1, 9, 0, 7, 6, 4, 5, 2]
 98 :   8 :  [8, 3, 1, 9, 0, 7, 6, 4, 5, 2, 10]
end :   3 :  [3, 1, 9, 0, 7, 6, 4, 5, 2, 10, 8]
oosterwal
  • 1,479
  • 8
  • 16
  • I like the idea of a 'pseudo-append'. I worry that if a song starts off at the end of the shuffled list, these pseudo-appends will, on average, tend to keep it near to the end, potentially for a long time, keeping it from ever making it to the front. I guess that's why you want to ensure that some are 'truly appended'. Be interesting to see what impact tweaking those proportions had on the resulting distribution. – James Hart Mar 29 '11 at 13:40
  • @James Hart: Songs that start near the end would quickly move forward to a place where they are no longer at risk of being pre-empted. When I get a chance, I'll update my answer to provide more detail... – oosterwal Mar 29 '11 at 13:48
  • @James Hart: I added working Python code and a sample run. You can see in the run that even when 'appending' just-played songs near the end, no song lingers at the back of the list very long. – oosterwal Mar 30 '11 at 13:10
3

My idea is to have a queue of cards to be played. The queue is shuffled and then played one at a time until emptied. As each card is being played, if the card was played less than m turns ago add it to the end of the queue and pick the next card. Once the queue is emptied it can be filled again and reshuffled. An array can be used to keep track of what turn a card was last played at. This runs O(1) per song on average.

Here's my solution in F#.

let deal (deck : _[]) m =
    let played = Array.create (deck.Length) (-m)

    let rec subDeal (cards : Queue<_>) i = 
        seq {
            if cards.Count = 0 then
                yield! subDeal (shuffledQueue deck) i
            else
                let card = cards.Dequeue()

                if i - played.[card] > m then
                    played.[card] <- i
                    yield card
                else
                    cards.Enqueue card

                yield! subDeal cards (i + 1)
        }

    subDeal (shuffledQueue deck) 1

Some test data for a deal of 0 .. 7 with m = 4.

[|3; 1; 4; 0; 2; 6; 5; 4; 0; 2; 3; 6; 1; 5; 0; 1; 2; 6; 4; 3; 5; 2; 0; 6; 3; 4;
  5; 1; 6; 0; 3; 2; 5; 4; 1; 3; 5; 2; 0; 6; 1; 4; 2; 5; 3; 4; 0; 1; 6; 5; 2; 4;
  3; 0; 6; 1; 3; 5; 6; 2; 4; 1; 0; 5; 2; 6; 3; 1; 4; 0; 2; 6; 1; 4; 0; 5; 3; 2;
  1; 0; 5; 6; 4; 3; 2; 1; 3; 0; 5; 6; 4; 3; 1; 2; 0; 5; 6; 4; 3; 0; ...|]

// card number and the number of occurrences of said card
[|(3, 286); (6, 286); (5, 285); (0, 286); (1, 285); (4, 286); (2, 286)|]

// longest time before each card is repeated
[|11; 11; 11; 11; 12; 11; 11|]

Full test program.

open System
open System.Collections.Generic

let rnd = new Random()

let shuffle cards =
    let swap (a: _[]) x y =
        let tmp = a.[x]
        a.[x] <- a.[y]
        a.[y] <- tmp

    Array.iteri (fun i _ -> swap cards i (rnd.Next(i, Array.length cards))) cards
    cards

let shuffledQueue cards =
    let queue = new Queue<_>()

    cards 
    |> shuffle 
    |> Array.iter (fun x -> queue.Enqueue x)
    queue

let deal (deck : _[]) m =
    let played = Array.create (deck.Length) (-m)

    let rec subDeal (cards : Queue<_>) i = 
        seq {
            if cards.Count = 0 then
                yield! subDeal (shuffledQueue deck) i
            else
                let card = cards.Dequeue()

                if i - played.[card] > m then
                    played.[card] <- i
                    yield card
                else
                    cards.Enqueue card

                yield! subDeal cards (i + 1)
        }

    subDeal (shuffledQueue deck) 1

let size = 7
let deck = Array.init size (fun i -> i)
let cards = deal deck 4

let getMaxWait seq value =
    Seq.fold (fun (last, count) test -> 
        if test = value then 
            (0, count) 
        else 
            (last + 1, max (last+1) count)
    ) (0, 0) seq
    |> snd

let test = cards |> Seq.take 2000

test
|> Seq.take 200
|> Seq.toArray
|> printfn "%A"

test
|> Seq.countBy (fun x -> x)
|> Seq.toArray
|> printfn "%A"

deck
|> Seq.map (fun x -> getMaxWait test x)
|> Seq.toArray
|> printfn "%A"

Console.ReadLine() |> ignore
gradbot
  • 13,732
  • 5
  • 36
  • 69
  • I like the way this explicitly keeps items moving forward, and that gives a strong sense that you'll eventually see them all - but with explicit checking to police that they don't appear too soon. This approach has the advantage of being demonstrably -correct-, then. But... hmm - maybe O(1) on average, but O(n) one time in n, which - for, say, a large MP3 collection (as opposed to a deck of 52 playing cards) - might be a pretty expensive operation. And O(n) additional storage, of course... – James Hart Mar 29 '11 at 13:58
  • I don't see a way around the O(n) behavior because of the nature of a shuffle. You could use a dictionary to replace the played array. Then slowly fill the cards queue with random cards that don't exist in the played dictionary to get the initial random set of cards but randomly picking the last few cards will get expensive. I found a related question http://stackoverflow.com/questions/1816534/random-playlist-algorithm – gradbot Mar 29 '11 at 22:04