Иногда у вас есть набор предметов — это могут быть строки, числа или числа, что угодно, порядок которых вы хотите рандомизировать. Это особенно полезно для викторин и азартных игр, но пригодится во всех других приложениях. Самый простой способ, который я нашел для этого, — вставить все элементы в массив, а затем перетасовать его, как колоду карт. Но как мы можем это сделать …?
В качестве простого примера мы будем использовать буквы алфавита:
|
1
|
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»];
|
Существуют разные подходы к сортировке массива.
Наивный подход
Мы могли бы создать второй массив и скопировать каждый элемент первого в случайную позицию во втором:
Код для этого может выглядеть следующим образом (см. Этот Быстрый совет по получению случайного целого числа в пределах определенного диапазона для более подробной информации):
|
1
2
3
4
5
6
7
8
9
|
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»];
var shuffledLetters:Array = new Array(letters.length);
var randomPos:int = 0;
for (var i:int = 0; i < letters.length; i++)
{
randomPos = int(Math.random() * letters.length);
shuffledLetters[randomPos] = letters[i];
}
|
Но есть одна огромная проблема. Что если случайная позиция, выбранная для C равна 6?
Здесь A перезаписывается и, следовательно, не будет в перемешанном массиве. Это не то, что мы хотим, поэтому мы должны проверить, что слот пуст, прежде чем копировать письмо, и выбрать другой слот, если это не так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
|
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»];
var shuffledLetters:Array = new Array(letters.length);
var randomPos:int = 0;
for (var i:int = 0; i < letters.length; i++)
{
randomPos = int(Math.random() * letters.length);
while (shuffledLetters[randomPos] != null) //repeat as long as the slot is not empty
{
randomPos = int(Math.random() * letters.length);
}
shuffledLetters[randomPos] = letters[i];
}
|
Это работает. Проблема в том, что это неэффективно. Видите, буква A гарантированно помещается в выбранный слот, потому что это первая выбранная буква, поэтому все слоты будут пустыми. С B есть шанс 25 на 26, что первый выбранный слот будет пустым. Когда мы на полпути к алфавиту, этот шанс падает до 50/50. К тому времени, когда мы достигнем V , есть вероятность 50/50, что мы не найдем пустой слот до четвертой попытки.
Это означает, что мы, скорее всего, будем вызывать Math.random() wayyyyy более 26 раз. И Math.random() является относительно медленной функцией. Какой другой подход мы можем использовать?
Подход среднего человека
Что если бы мы сохранили список всех пустых слотов в третьем массиве, который уменьшился бы при их просмотре?
… и так далее, повторяя, пока массив пустых слотов не содержит элементов. Код для этого будет выглядеть так:
|
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
|
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»];
var shuffledLetters:Array = new Array(letters.length);
var emptySlots:Array = new Array();
for (var n:int = 0; n < letters.length; n++)
{
emptySlots.push(n);
}
var randomPos:Number = 0;
var actualSlot:Number = 0;
for (var i:int = 0; i < letters.length; i++)
{
randomPos = int(Math.random() * emptySlots.length);
actualSlot = emptySlots[randomPos];
shuffledLetters[actualSlot] = letters[i];
emptySlots.splice(randomPos, 1);
}
|
Здесь мы используем метод Array.splice () для удаления одного элемента из списка пустых слотов. Это фактически удаляет элемент, а не просто устанавливает его значение равным null ; поэтому после объединения первого слота emptySlots.length будет 25 а не 26 .
Эта функция splice() великолепна; мы можем использовать это для третьего подхода к тасованию, который исключает этот массив среднего человека.
Сплайсинговый подход
Вместо того, чтобы удалять элементы из массива пустых слотов, когда мы закончили с ними, мы могли бы удалить их из исходного массива без перетасовки.
Поначалу это звучит не очень полезно — но что, если мы выбрали случайные элементы из исходного массива вместо случайного выбора их пунктов назначения ?
… и так далее, пока первый массив не содержит элементов.
В отличие от двух других подходов, мы получаем без исходного массива. Является ли это проблемой или нет, зависит от этого проекта.
Код может выглядеть так:
|
01
02
03
04
05
06
07
08
09
10
|
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»];
var shuffledLetters:Array = new Array(letters.length);
var randomPos:Number = 0;
for (var i:int = 0; i < shuffledLetters.length; i++) //use shuffledLetters.length because splice() will change letters.length
{
randomPos = int(Math.random() * letters.length);
shuffledLetters[i] = letters[randomPos];
letters.splice(randomPos, 1);
}
|
Фактически, поскольку splice() возвращает Array всех элементов, которые вы объединяете, мы могли бы немного упростить код:
|
1
2
3
4
5
6
7
8
9
|
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»];
var shuffledLetters:Array = new Array(letters.length);
var randomPos:Number = 0;
for (var i:int = 0; i < shuffledLetters.length; i++)
{
randomPos = int(Math.random() * letters.length);
shuffledLetters[i] = letters.splice(randomPos, 1)[0];
}
|
Это аккуратнее. У меня есть еще один подход, которым можно поделиться; этот очень отличается от других, которые мы использовали до сих пор.
Сортировочный подход
Массивы имеют метод sort () , который по умолчанию переставляет все элементы массива в возрастающем алфавитно-цифровом порядке, например так:
|
1
2
3
|
var mixedLetters:Array = [«G», «B», «P», «M», «F»];
mixedLetters.sort();
//mixedLetters is now [«B», «F», «G», «M», «P»]
|
Вы можете передать параметры этому методу, например Array.DESCENDING , который меняет порядок сортировки:
|
1
2
3
|
var mixedLetters:Array = [«G», «B», «P», «M», «F»];
mixedLetters.sort(Array.DESCENDING);
//mixedLetters is now [«P», «M», «G», «F», «B»]
|
(Существуют и другие варианты , и вы можете передать их столько, сколько захотите.)
Вы также можете передать ссылку на функцию , которая сообщает Flash, как решить, к какому порядку относятся любые два элемента. Например, эту функцию можно использовать для числовой сортировки:
|
1
2
3
4
5
6
|
function numericalSort(a:Number, b:Number):Number
{
if (a < b) return -1;
if (a == b) return 0;
if (a > b) return 1;
}
|
Flash просматривает каждую пару соседних элементов в массиве и переставляет их в соответствии с этой функцией: он меняет их местами, если возвращается значение 1 , и оставляет их в покое в противном случае. (Если вы не передадите Array.DESCENDING а также функцию, в этом случае она меняет местами их, если возвращается значение -1 , и оставляет их в покое в противном случае.) Flash повторяет это по всему массиву снова и снова, пока все пары не вернут 0 или -1 ( 0 или 1 если используется Array.DESCENDING ).
Мы можем связываться с этим. Вместо того, чтобы указывать истинную причину, по которой любые два элемента должны быть поменяны местами, мы можем просто сказать, чтобы они менялись местами случайным образом, используя функцию сортировки, подобную этой:
|
1
2
3
4
5
|
function randomSort(a:*, b:*):Number //* means any kind of input
{
if (Math.random() < 0.5) return -1;
else return 1;
}
|
Легко! Теперь мы можем использовать его в нашем коде так:
|
01
02
03
04
05
06
07
08
09
10
|
function randomSort(a:*, b:*):Number
{
if (Math.random() < 0.5) return -1;
else return 1;
}
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»];
letters.sort(randomSort);
//(no need for the shuffledLetters[] Array)
|
Обратите внимание, что результирующий массив не будет случайным образом перетасовываться, как другие используемые нами подходы — в этом подходе нет даже 1/26 вероятности того, что любая данная буква окажется в любом данном слоте. Это потому, что мы меняем только смежные пары элементов и делаем не более того. Тем не менее, это аккуратный метод 🙂
Есть много других методов, я знаю. Есть что-нибудь, что тебе нравится больше, чем эти?
Редактировать: Вот отличный пост с некоторыми очень классными визуализациями, объясняющими случайную случайность Фишера-Йейтса, которая работает на месте. Я очень рекомендую это!