Consejo rápido: Cómo barajar aleatoriamente una matriz en AS3

A veces tienes un conjunto de elementos, podrían ser cadenas, números, objetos, lo que sea, cuyo orden deseas aleatorizar. Esto es particularmente útil para pruebas y juegos de azar, pero es útil en todo tipo de otras aplicaciones. El método más fácil que he encontrado para hacer esto es pegar todos los elementos en una matriz y luego barajarlos como una baraja de cartas. Pero, ¿cómo podemos hacer eso?

Como ejemplo simple, usaremos las letras del alfabeto:

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

Hay diferentes enfoques que podemos tomar para clasificar realmente esta matriz.

El enfoque ingenuo

Podríamos crear una segunda matriz y copiar cada elemento del primero en una posición aleatoria en el segundo:

El código para esto podría tener este aspecto (consulta este Consejo rápido para obtener un número entero aleatorio dentro de un rango específico para obtener más detalles):

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

3

var shuffledLetters:Array = new Array(letters.length);

4

5

var randomPos:int = 0;

6

for (var i:int = 0; i < letters.length; i++)

7

{

8

	randomPos = int(Math.random() * letters.length);

9

	shuffledLetters[randomPos] = letters[i];

10

}

Pero hay un gran problema. ¿Qué pasa si la posición aleatoria elegida para C también es 6?

Aquí, A se sobrescribe y, por lo tanto, no estará en la matriz aleatoria. Eso no es lo que queremos, por lo que debemos verificar que la ranura esté vacía antes de copiar la carta y elegir una ranura diferente si no es así:

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

3

var shuffledLetters:Array = new Array(letters.length);

4

5

var randomPos:int = 0;

6

for (var i:int = 0; i < letters.length; i++)

7

{

8

	randomPos = int(Math.random() * letters.length);

9

	while (shuffledLetters[randomPos] != null)		//repeat as long as the slot is not empty

10

	{

11

		randomPos = int(Math.random() * letters.length);	//pick a different slot

12

	}

13

	shuffledLetters[randomPos] = letters[i];

14

}

Eso funciona. El problema es que es ineficiente. Verás, la letra A está garantizada para encajar en la ranura elegida, porque es la primera letra elegida, por lo que todas las ranuras estarán vacías. Con B, hay una probabilidad de 25 en 26 de que la primera ranura elegida esté vacía. Cuando estamos a la mitad del alfabeto, esta posibilidad se reduce a 50/50. Para cuando lleguemos a V, hay una probabilidad de 50/50 de que no encontremos un espacio vacío hasta el cuarto intento.

Esto significa que es muy probable que llamemos a Math.random() y que haga el trayecto más de 26 veces. Y Math.random() es una función relativamente lenta. ¿Qué otro enfoque podemos tomar?

El enfoque del intermediario

¿Qué pasa si almacenamos una lista de todas las ranuras vacías en una tercera matriz, que se reduciría a medida que las revisáramos?

...y así sucesivamente, repitiendo hasta que la matriz de ranuras vacías no contenga elementos. El código para eso se vería así:

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

3

var shuffledLetters:Array = new Array(letters.length);

4

5

var emptySlots:Array = new Array();

6

for (var n:int = 0; n < letters.length; n++)

7

{

8

	emptySlots.push(n);

9

}

10

11

var randomPos:Number = 0;

12

var actualSlot:Number = 0;

13

for (var i:int = 0; i < letters.length; i++)

14

{

15

	randomPos = int(Math.random() * emptySlots.length);		//note emptySlots.length not letters.length

16

	actualSlot = emptySlots[randomPos];

17

	shuffledLetters[actualSlot] = letters[i];

18

	emptySlots.splice(randomPos, 1);

19

}

Aquí usamos el método Array.splice() para eliminar un solo elemento de la lista de ranuras vacías. Esto realmente elimina el elemento, en lugar de simplemente establecer su valor en null; entonces, después de empalmar la primera ranura, emptySlots.length será 25 en lugar de 26.

Esta función splice() es genial; podemos usarlo para un tercer enfoque de barajado que elimina esta matriz de intermediarios.

El enfoque de empalme

En lugar de eliminar elementos del conjunto de ranuras vacías cuando hayamos terminado con ellos, podríamos eliminarlos del conjunto original sin mezclar.

Esto no suena muy útil al principio, pero ¿qué pasa si elegimos elementos de la matriz original al azar, en lugar de elegir sus destinos al azar?

...y así sucesivamente, hasta que la primera matriz no contenga elementos.

A diferencia de los otros dos enfoques, terminamos sin la matriz original. Si esto es un problema o no depende de este proyecto.

El código podría verse así:

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

3

var shuffledLetters:Array = new Array(letters.length);

4

5

var randomPos:Number = 0;

6

for (var i:int = 0; i < shuffledLetters.length; i++)	//use shuffledLetters.length because splice() will change letters.length

7

{

8

	randomPos = int(Math.random() * letters.length);

9

	shuffledLetters[i] = letters[randomPos];	//note this the other way around to the naive approach

10

	letters.splice(randomPos, 1);

11

}

De hecho, dado que splice() devuelve una matriz (un Array) de todos los elementos que estás empalmando, podríamos simplificar un poco el código:

1

2

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

3

var shuffledLetters:Array = new Array(letters.length);

4

5

var randomPos:Number = 0;

6

for (var i:int = 0; i < shuffledLetters.length; i++)

7

{

8

	randomPos = int(Math.random() * letters.length);

9

	shuffledLetters[i] = letters.splice(randomPos, 1)[0];	//since splice() returns an Array, we have to specify that we want the first (only) element

10

}

Eso es más ordenado. Tengo un enfoque más para compartir; Este es muy diferente a los otros que hemos usado hasta ahora.

El enfoque del ordenamiento

Las matrices tienen un método, sort(), que por defecto reorganiza todos los elementos de la matriz en orden alfanumérico ascendente, de esta manera:

1

2

var mixedLetters:Array = ["G", "B", "P", "M", "F"];

3

mixedLetters.sort();

4

//mixedLetters is now ["B", "F", "G", "M", "P"]

Puedes pasar opciones a este método, como Array.DESCENDING, que invierte el orden de clasificación:

1

2

var mixedLetters:Array = ["G", "B", "P", "M", "F"];

3

mixedLetters.sort(Array.DESCENDING);

4

//mixedLetters is now ["P", "M", "G", "F", "B"]

(Hay otras opciones, y puedes pasar tantas como desees).

También puedes pasar una referencia a una función, que le dice a Flash cómo decidir en qué orden pertenecen los dos elementos. Por ejemplo, esta función podría usarse para la ordenación numérica:

1

2

function numericalSort(a:Number, b:Number):Number

3

{

4

	if (a < b) return -1;

5

	if (a == b) return 0;

6

	if (a > b) return 1;

7

}

Flash analiza cada par de elementos adyacentes en la matriz y los reorganiza de acuerdo con esta función: los intercambia si se devuelve el valor 1 y, de lo contrario, los deja solos. (A menos que pases Array.DESCENDING así como la función, en cuyo caso los intercambia si se devuelve el valor -1 y los deja solos de lo contrario.) Flash repite esto en toda la matriz una y otra vez hasta que todos los pares devuelvan 0 o -1 (0 o 1 si usas Array.DESCENDING).

Podemos meternos con esto. En lugar de darle una razón genuina por la cual se deben intercambiar dos elementos, podemos decirle que los intercambie al azar, usando una función de ordenamiento como esta:

1

2

function randomSort(a:*, b:*):Number	//* means any kind of input

3

{

4

	if (Math.random() < 0.5) return -1;

5

	else return 1;

6

}

¡Fácil! Ahora podemos usarlo en nuestro código así:

1

2

function randomSort(a:*, b:*):Number

3

{

4

	if (Math.random() < 0.5) return -1;

5

	else return 1;

6

}

7

8

var letters:Array = ["A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z"];

9

letters.sort(randomSort);

10

11

//(no need for the shuffledLetters[] Array)

Ten en cuenta que la matriz resultante no se barajará aleatoriamente como los otros enfoques que hemos utilizado; en este enfoque, no hay ni siquiera una probabilidad de 1/26 de que una letra determinada termine en un espacio determinado. Esto se debe a que solo intercambiamos pares de elementos adyacentes y no hacemos más que eso. Aún así, es un método ordenado :)

Hay muchos otros métodos, lo sé. ¿Tienes alguno que te guste más que estos?

Editar: Aquí hay una gran publicación con algunas visualizaciones muy interesantes, que explican la mezcla aleatoria de Fisher-Yates, que funciona en su lugar. ¡Lo recomiendo altamente!