Shuffle (Barajar) aleatoriamente
con el algoritmo Sattolo-Cycle un array en Gambas
Leyendo el artículo de Joedicastro (http://joedicastro.com/algoritmos-shuffle.html) sobre los distintos algoritmos de barajar arrays, donde define varios algoritmos, entre ellos el algoritmo Sattolo-Cycle:
"este algoritmo solo genera ciclos, de ahí su nombre. Es decir, reparte uniformemente los resultados solo entre algunas permutaciones que se van rotando (aunque comparte el mismo problema con los anteriores al depender de una aleatoriedad no perfecta). Para resumir su funcionamiento, lo que hace es que después de ejecutarlo, ningún elemento de la lista repite la posición anterior que tenía en la misma. Ese algoritmo fue publicado por Sandra Sattolo en 1986"
He aplicado dicho algoritmo a una función realizada en gambas, quedando el código siguiente:
' Gambas module file
Public
Function
barajar(listaOriginal
As
Variant[])
As
Variant[]
Dim
listatemporal
As
New
Variant[]
Dim
i,
idx,
sel
As
Integer
'1º
asigna a la listaOriginal a la temporal
For
i
=
0
To
listaOriginal.max
listatemporal.add(listaOriginal[i])
'usa una lista
temporal para no perder el orden original'
Next
'2º
mezcla algoritmo Sattolo-Cycle
idx
=
listaOriginal.count
While
idx
>
1
idx
=
idx
-
1
sel
=
Int(Rnd(0,
idx))
Swap
listatemporal[sel],
listatemporal[idx]
'intercambio
valores
Wend
Return
listatemporal
'se devuelve la
lista temporal que es la lista originnal mezclada
End
Como veis esta función recibe un array de elementos, como es variant[] admite arrays de todo tipo: int[],float[],string[], structure[], objet[] y por supuesto vaiant[], y devuelve ese array barajado.
Ejemplo:
Un pequeño ejemplo de aplicación de shuffle (o "barajar") es el siguiente, tenemos una lista de 5 cadenas: "0/4", "1/4", "2/4", "3/4" y "4/4". Y queremos barajarlo varias veces.
Usaríamos este código:
Public
Sub
barajo()
Dim
a
As
Integer
Dim
lista
As
New
String[]
Dim
listaBarajada
As
String[]
Randomize
lista.Add("0/4")
lista.Add("1/4")
lista.Add("2/4")
lista.Add("3/4")
lista.Add("4/4")
TextLabel1.text
=
"--------
Inicialmente ----------" &
"<br>"
For
a
=
0
To
lista.Max
TextLabel1.text
&=
lista[a]
&
"<br>"
Next
listaBarajada
=
ModuleAzar.barajar(lista)
TextLabel1.text
&=
"--------
Barajo ----------" &
"<br>"
For
a
=
0
To
lista.Max
TextLabel1.text
&=
listaBarajada[a]
&
"<br>"
Next
TextLabel1.text
&=
"--------
Barajo ----------" &
"<br>"
listaBarajada
=
ModuleAzar.barajar(listaBarajada)
'barajo sobre
la lista bajada anteriormente, para no repetir posicion
For
a
=
0
To
lista.Max
TextLabel1.text
&=
listaBarajada[a]
&
"<br>"
Next
End
El resultado seria:
Código fuente completo: enlace a google drive
En un próximo post, os presentaré un juego que hace uso de este algoritmo.
Fuentes:
http://joedicastro.com/algoritmos-shuffle.html
