如何實現隨機 - 但不是太隨機的重複洗牌

Question

我有一個n項目的列表。我想算法讓我挑隨機從藏品的一個潛在的無限序列，但有幾個限制：

1. 一旦項目已被摘下來，它不應該再在接下來的轉起來幾個項目（比如說在未來米項目，與米明顯嚴格< ñ）
2. 你不應該等待很長時間，任何項目出現 - 項目應出現在平均每ñ挑選
3. 該序列應該是非循環的

基本上，我想要一個算法來生成MP3播放器的播放列表，並打開'shuffle'和'repeat'，確保它不會播放同一首歌曲太靠近自己，並確保它均勻地播放所有歌曲，沒有可辨別的模式。

這些制約消除爭兩個明顯的解決方案：

• 我們不能簡單地挑RND（ñ）作爲下一個項目的索引，因爲這將無法保證不重複;它可能需要很長時間來挑選一些項目。
• 我們不能只用Fisher-Yates shuffle預先洗牌，反覆迭代它，每當我們達到結束時重新洗牌;雖然保證物品最多在2n - 1揀配後出現，但並不能完全防止物品重複。

一個天真的解決方案可能是隨機挑選，但拒絕選秀權，如果他們發生在上米選秀權;這意味着保持先前選擇的清單，並且每次對照該清單檢查每個選擇，這使得該算法同時不確定並且緩慢 - 丟失。除非我錯過了一些明顯的東西。

所以我有一個我現在使用的算法，我有點不滿意。我用一副牌作爲比喻來推導它，在這裏我有一個平鋪和丟棄堆。我從整個清單開始，在拖曳堆裏，拖着一堆廢棄的紙堆。接下來的項目從繪圖堆的頂部讀取，然後放入廢棄堆中。一旦棄牌堆達到一定的尺寸（m項目），我將它洗牌並將其移動到抽籤堆的底部。

這符合要求，但洗牌一次m選秀困擾我。它通常是O（1），但是O（m）是m的一次。平均而言，這相當於不變的時間，但必須有一個更清潔的解決方案，隨時拋棄丟棄物。

在我看來，這是一個簡單，普遍和常見的問題，它必須有一個雙管算法，如Fisher-Yates或Boyer-Moore。但我的google-fu顯然不夠強大，因爲我還沒有找到找到不可避免的1973年ACM論文的一組術語，這可能解釋瞭如何在O（1）時間內做到這一點，以及爲什麼我的算法存在嚴重缺陷某種程度上來說。

Answer 1

要生成列表做到以下幾點。有一個平局和丟棄堆。最初丟棄堆是空的。隨機抽取你的第一件物品。將它添加到播放列表中，然後放入放棄堆中。當丟棄堆中有m個物品時，從丟棄堆中取出最後一個物品（最近最少使用）並將其添加到拖放堆中。播放列表將是隨機的，但不需要隨機播放。

這是紅寶石：

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 

編輯：添加playlist_of_length方法，使其更清晰，你怎麼稱呼NEXT_ITEM生成播放列表

Answer 2

打一個給定的歌曲後，用僞追加將其放置在靠近列表的末尾。您可能需要將大約1/2到2/3的數據真正地附加到列表中的最後5個項目內，並將其他1/3到1/2的數據分散。

顯然，這不會很短名單的工作，但應爲10個或多個列表被罰款。

---

編輯（提供有關「PseudoAppend」更詳細）：

下面的僞代碼使用的語言結構的組合，但應該很容易轉變成實際的代碼。

定列表[歌曲]

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 

從列表中刪除剛剛完成的歌曲，而不必首先備份列表可能會導致信息丟失，但這是爲了傳達一個想法，只是僞代碼。

正如你所看到的，剛播放的歌曲將被移動到列表後面的時間的2/3，而將未來的最後一首歌的移動時間的1/3。

這首歌向前移動1/3的機會，時間2/3它只會提前一首歌，和當時的其他1/3將提前移動的兩個或更多歌曲。這首歌曲移動到最後位置的機會= 66％，倒數第二位置= 22％，倒數第三位= 12％。

的PseudoAppend的實際行爲是所有While語句的條件範圍內加以管轄。您可以更改值來比較的random數生成器，使其或多或少可能是一首歌移動佔先機，你可以改變相比target值調整多遠剛剛完成的歌曲可以在向前邁進列表。

---

編輯II（用於11個項目的列表的Python代碼3和樣本輸出）

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) 

下面是通過列表〜9倍運行的示例輸出。第一列是一個簡單的運行指標，第二欄顯示當前選擇的歌曲，第三列顯示列表的當前順序：

>>> ================================ 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] 

Answer 3

我的想法是有卡隊列被播放。隊列被洗牌，然後一次播放一次，直到排空。當每張卡片正在播放時，如果卡片的播放時間少於m個，則將其添加到隊列末尾並選取下一張卡片。一旦隊列被清空，它可以再次填充並重新洗牌。一個數組可以用來跟蹤上次玩卡的情況。這將平均每首歌曲運行O（1）。

這是我在F＃中的解決方案。

爲0的協議一些測試數據。7，其中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|] 

完整測試程序。

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 

Answer 4

除了隊列算法implemententation和視覺驗證

在數學：

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] 

讓我們來看看，有沒有明顯的重複模式：

個比較不同的週期長度：

Answer 5

這可能是你在找什麼。

Never-ending Shuffled Sequences

網站消失了，但這裏是存檔，因爲該鏈接已經被其他地方引用。 Archive.org