algorithm - tipos - numeros aleatorios google

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

Question

Tengo una lista de n elementos. Quiero un algoritmo que me permita elegir al azar una secuencia infinita de elementos de esa colección al azar, pero con un par de restricciones:

1. una vez que un artículo ha sido recogido, no debe volver a aparecer en los siguientes artículos (por ejemplo, en los próximos m elementos, con m obviamente estrictamente < n )
2. no debería tener que esperar demasiado para que aparezca ningún artículo; los artículos deberían 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 ''shuffle'' y ''repeat'' activado, que asegura que no reproduzca la misma canción demasiado cerca de sí mismo, y se asegura de que reproduce todas tus canciones de manera uniforme , sin un patrón discernible.

Esas limitaciones eliminan dos soluciones obvias de la contención:

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

Una solución ingenua podría ser escoger al azar pero rechazar selecciones si ocurrieron en los últimos m ; eso significa mantener una lista de m selecciones anteriores, y verificar cada selección contra esa lista cada vez, lo que hace que el algoritmo no sea determinista y lento al mismo tiempo - perder-perder. A menos que me pierda 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 cierto tamaño ( m elementos), la arrastro y la muevo al fondo de la pila de sorteo.

Esto cumple con el requisito, pero eso se mezcla una vez que cada m me molesta. Es O (1) normalmente, pero O (m) una vez en m. Eso equivale a 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, que 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

Después de reproducir una canción determinada, use un pseudo-apéndice 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 (proporciona más detalles sobre ''PseudoAppend''):

El siguiente pseudocódigo utiliza una combinación de construcciones de lenguaje, pero debe ser lo suficientemente fácil como para convertirse en código real.

Given List [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

Eliminar la canción recién completada de la lista sin tener primero una lista de respaldo puede ocasionar la pérdida de información, pero esto es solo un pseudocó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 de 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 que una canción, y la otra 1/3 del tiempo se moverá antes que 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 sentencia 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 adecue a otras, y puede cambiar el valor en comparación con el target para ajustar hasta dónde puede avanzar la canción recién completada en la lista.

Editar II (código de Python 3 y salida de muestra para una lista de 11 elementos)

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)

Aquí hay un resultado de muestra que se ejecuta en la lista ~ 9 veces. La primera columna es simplemente un índice en ejecución, la segunda columna muestra la canción seleccionada actualmente, 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 2

Mi idea es tener una cola de cartas para jugar. 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 #.

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

Algunos datos de prueba para un trato 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 prueba 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 3

Además de la implementación del algoritmo de cola y la 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]

Veamos que no hay patrones repetitivos obvios:

Comparando diferentes longitudes de ciclos:

Answer 4

Para generar su 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 sorteos. 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 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

EDITAR: Se agregó el método playlist_of_length para que quede más claro cómo se llama a next_item para generar la lista de reproducción

Answer 5

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

Secuencias barajadas interminables

El sitio se ha ido, pero aquí está el archivo ya que este enlace ha sido referenciado en otro lugar. Archive.org