Cómo implementar una mezcla repetitiva que es aleatoria, pero no demasiado aleatoria

Question

Tengo una lista de n elementos. Quiero un algoritmo para dejar a escoger una secuencia potencialmente infinito de artículos de esa colección al azar, pero con un par de limitaciones:

1. una vez que un artículo ha sido recogido, no debería aparecer de nuevo en la próxima algunos artículos (digamos en la siguiente m artículos, con m obviamente estrictamente < n)
2. que no deberían tener que esperar demasiado tiempo para que aparezca cualquier artículo - los artículos deben aparecer en promedio una vez cada n selecciones
3. la secuencia debe ser no-cíclica

Básicamente, quiero un algoritmo para generar la lista de reproducción para un reproductor de MP3 con 'aleatorio' y 'repetición' encendido, que se asegura de que no desempeña la misma canción demasiado cerca de sí mismo, y se asegura de que reproduce todas sus canciones de manera uniforme, sin un patrón discernible.

Esas restricciones eliminan dos soluciones obvias de contención:

• No podemos tomar simplemente rnd ( n) como índice para el siguiente elemento, ya que no va a garantizar la no repetición; también puede llevar mucho tiempo elegir algunos artículos.
• No podemos simplemente mezclar previamente la lista con una combinación aleatoria de Fisher-Yates, e iterar sobre ella repetidamente, reorganizándola cada vez que llegamos al final; mientras que eso garantiza que los elementos aparezcan como máximo después de 2n - 1 selecciones, no impide por completo la repetición de un artículo.

Una solución podría ser ingenuo para recoger al azar, sino rechazar picos si se produjeron en la última m picos; eso significa mantener una lista de m selecciones anteriores, y comprobar cada selección contra esa lista cada vez, lo que hace que el algoritmo no determinista y lento al mismo tiempo - perder-perder. A menos que me falta algo obvio ..

Así que tengo un algoritmo que estoy usando ahora con el que estoy un poco insatisfecho. Lo he derivado por analogía con una baraja de cartas, donde tengo un montón de sorteo y una pila de descartes. Empiezo con la lista completa, mezclada, en la pila de sorteo, la pila de descarte vacía. El siguiente elemento se lee desde la parte superior de la pila de sorteo, y luego se coloca en la pila de descarte. Una vez que la pila de descarte alcanza un cierto tamaño (m elementos), lo barao y lo muevo al pie de la pila de sorteo.

Esto cumple con el requisito, pero esa mezcla una vez cada m selecciones me molesta. Es O (1) normalmente, pero O (m) una vez en m. Eso equivale a un tiempo constante, en promedio, pero debe haber una solución más limpia que mezcle los descartes a medida que avanza.

Me parece que este es un problema tan simple, genérico y común, debe tener uno de esos algoritmos de doble cañón, como Fisher-Yates o Boyer-Moore. Pero mi google-fu claramente no es fuerte, ya que todavía tengo que encontrar el conjunto de términos que ubica el inevitable documento de ACM de 1973 que probablemente explica exactamente cómo hacerlo en O (1) vez, y por qué mi algoritmo está muy dañado. de alguna manera.

Answer 1

Para generar la lista haga lo siguiente. Toma un sorteo y descarta la pila. Inicialmente, la pila de descarte está vacía. Elige tu primer objeto al azar de la pila de sorteo. Agrégalo a la lista de reproducción y luego ponlo en la pila de descarte. Cuando hay m elementos en la pila de descarte, toma el último elemento (menos utilizado recientemente) de la pila de descarte y agrégalo a la pila de sorteo. La lista de reproducción será aleatoria, pero no se requiere reproducción aleatoria.

Aquí está en rubí:

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: Añadido método playlist_of_length para que sea más clara de cómo se llama NEXT_ITEM para generar la lista de reproducción

Answer 2

Después de reproducir una canción determinada, use un pseudoapendio para colocarla cerca del final de la lista. Es probable que desee que se agregue aproximadamente 1/2 a 2/3 y el otro 1/3 a 1/2 se extienda dentro de los últimos 5 o más elementos de la lista.

Obviamente esto no funcionará para listas muy cortas, pero debería estar bien para listas de 10 o más.

---

Editar (proporcione más detalles sobre 'PseudoAppend'):

El siguiente pseudo-código utiliza una mezcla de construcciones del lenguaje, pero debería ser bastante fácil de convertir en código real.

lista dada [canciones]

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 

Extracción de la canción que acaba de terminar de la lista sin tener primero una lista de copia de seguridad puede resultar en la pérdida de información, pero esto es sólo pseudo-código destinado a transmitir una idea.

Como puede ver, 2/3 de las veces la canción que acaba de reproducirse se moverá al final de la lista, y 1/3 de las veces se moverá antes que la última canción.

De la posibilidad de 1/3 de que la canción se mueva hacia adelante, 2/3 de las veces solo se moverá antes de una canción, y la otra 1/3 de las veces se moverá delante de dos o más canciones Oportunidad de que la canción se mueva a la última posición = 66%, penúltima = 22%, penúltima = 12%.

El comportamiento real del PseudoAppend está regido por la condición de la declaración While. Puede cambiar el valor para compararlo con el generador de números random para que sea más o menos probable que una canción se mueva antes que otras, y puede cambiar el valor en comparación con target para ajustar cuánto puede avanzar la canción recién completada en la lista.

---

Editar II (Python 3 de código y muestra de salida de una lista de 11 artículos)

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) 

He aquí un ejemplo de salida que atraviesa la lista ~ 9 veces. La primera columna es simplemente un índice de carrera, la segunda columna muestra la canción seleccionada en ese momento, y la tercera columna muestra el orden actual de la lista:

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

Mi idea es tener una cola de tarjetas de ser jugado. La cola se baraja y luego se reproduce de uno en uno hasta que se vacíe. A medida que se juega cada carta, si la tarjeta se jugó hace menos de m vueltas, agréguela al final de la cola y elija la siguiente.Una vez que se vacía la cola, puede llenarse nuevamente y reorganizarse. Se puede usar una matriz para realizar un seguimiento del giro en el que se jugó la última carta. Esto ejecuta O (1) por canción en promedio.

Aquí está mi solución en F #.

algunos datos de prueba para una cantidad de 0 .. 7 con 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|] 

programa de pruebas completo.

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

Aparte cola algoritmo implemententation y verificación visual

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

Vamos a ver que no hay obvios patrones repetitivos:

Comparación de ciclos diferentes longitudes:

Answer 5

Esto podría ser lo que estás buscando.

Never-ending Shuffled Sequences

sitio se ha ido, pero aquí es el archivo desde este enlace se ha hecho referencia en otros lugares. Archive.org