Как да приложите повтарящо се разбъркване, което е произволно - но не прекалено произволно

За да генерирате своя списък, направете следното. Имайте купчина теглене и изхвърляне. Първоначално купчината за изхвърляне е празна. Изберете първия си предмет на случаен принцип от купчината за теглене. Добавете го към списъка за игра и след това го поставете в купчината за изхвърляне. Когато има 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 за генериране на списъка за изпълнение

Внедряване на алгоритъм за опашка отстрани и визуална проверка

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

Нека видим, че няма очевидни повтарящи се модели:

Сравняване на различни дължини на цикли:

След възпроизвеждане на дадена песен използвайте псевдодобавка, за да я поставите близо до края на списъка. Вероятно ще искате около 1/2 до 2/3 да бъдат наистина добавени, а останалите 1/3 до 1/2 разпределени в рамките на последните 5 или повече елемента в списъка.

Очевидно това няма да работи за много кратки списъци, но трябва да е добре за списъци от 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, за да коригирате колко далеч току-що завършената песен може да се придвижи напред в Списъкът.

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]

Идеята ми е да има опашка от карти, които да се играят. Опашката се разбърква и след това се играе една по една, докато се изпразни. Докато всяка карта се играе, ако картата е била играна преди по-малко от m хода, добавете я в края на опашката и изберете следващата карта. След като опашката бъде изпразнена, тя може да бъде попълнена отново и разместена. Масивът може да се използва, за да се следи на кой ход е играна картата за последен път. Това работи средно O(1) на песен.

Ето моето решение във 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

Някои тестови данни за сделка от 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