How to implement a repeating shuffle that's random - but not too random
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:
- 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)
- you shouldn't have to wait too long for any item to appear - items should appear on average once every n picks 开发者_运维问答
- 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.
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
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:
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]
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
加载中,请稍侯......
精彩评论