Алгоритм перетасовки является распространенной случайной проблемой, с которой мы сталкиваемся во время игры в игры и случайной сортировки. Это можно абстрагировать так: получить массив случайного порядка всех натуральных чисел в М.
Поиск «алгоритма перестановки» на Baidu, первым результатом был «Библиотека Baidu - алгоритм перестановки». После сканирования содержимого многие из содержимого легко ввести в заблуждение других в заблуждение, включая использование связанных списков для замены массивов, что является лишь ограниченной оптимизацией (списки ссылок также вводят потерю эффективности чтения).
Первый метод в этой статье можно просто описать как: случайным образом рисовать карты и поместить их в другую группу; Нарисуйте их снова, нарисуйте их неоднократно, когда вы рисуете пустые карты.
«Нарисуйте карты после того, как снова их рисуют» приведет к увеличению вероятности рисования карт позже, что, очевидно, неразумно.
Один шаг может быть оптимизирован: после того, как карты будут нарисованы, оригинальные карты становятся меньше. (вместо того, чтобы оставлять пустые карты)
Код заключается в следующем:
Кода -копия выглядит следующим образом:
Функция shuffle_pick_1 (m) // метод рисования карты Shush //
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Нарисуйте по одной карте за раз и поместите ее в другую кучу. Поскольку вам необходимо извлечь элементы из массива и вытащить все последующие элементы вперед один за другим, это трудоемкое.
var arr2 = new Array ();
for (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
возврат ARR2;
}
Это также, очевидно, проблематично, потому что, если массив большой, удаление определенного элемента в середине приведет к тому, что очередь сделает шаг вперед, что является очень трудоемким действием.
Вспомните цель «Почему мы удаляем этот элемент?» Чтобы избежать пустых карт.
В дополнение к удалению этого элемента, есть ли у нас другие способы удаления пустых карт?
---- Да, нам просто нужно поместить последнюю расписанную карту в позицию розыгрыша.
Итак, мы можем оптимизировать эту идею следующим образом:
Кода -копия выглядит следующим образом:
Функция shuffle_pick (m) // shut // Метод рисования карт для оптимизации карты
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Нарисуйте по одной карте за раз и поместите ее в другую кучу. Поместите последнюю карту с невыполненностью на открытое сиденье.
var arr2 = new Array ();
for (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
возврат ARR2;
}
В дополнение к идее рисования карт, мы также можем использовать идею изменения карт.
«Алгоритм Baidu Wenku-Shut» упоминает идею об изменении карты: «Случай две позиции случайным образом, и обмениваться их в общее время. Чем больше N, тем ближе он к случайному».
Этот подход неверен. Даже если N очень большой (например, 10 карт, 10 коммутаторов), все еще существует высокая вероятность, что «некоторые карты вообще не меняют позиции».
Следуйте этой идее и сделайте небольшую корректировку: измените I-TH-карту на любую карту и просто измените ее на один раунд.
Код заключается в следующем:
Кода -копия выглядит следующим образом:
Функция shuffle_swap (m) // метод изменения карты shush //
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// i-th-карта используется для изменения сидений, и вы можете изменить ее на один раунд
для (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
возврат Arr;
}
В дополнение к идее рисования и смены карт, мы также можем использовать идею вставки карт: сначала есть одна карта, вторая карта имеет две позиции, которые будут вставлены случайным образом (до или позади первой карты), третья карта имеет три позиции, которые будут вставлены случайным образом (расположено или вставлено в первую позицию или вставлена в вторую позицию), и т. Д.
Код заключается в следующем:
Кода -копия выглядит следующим образом:
Функция shuffle_insert_1 (m) // shunt // Метод вставки карты
{
// Каждый раз самая большая карта генерируется и вставляется перед случайной картой. Поскольку вам нужно вставить элементы в массив и сжать все последующие элементы обратно один за другим, это требует много времени.
var arr = [0];
для (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
возврат Arr;
}
Приведенный выше код также будет иметь некоторые проблемы: по мере увеличения количества карт становится все труднее вставить карты, потому что вставка карт приведет к многим картам, которые следуют на один шаг назад.
Конечно, мы также можем правильно оптимизировать: сначала есть карта n-1, карта N-TH размещена в конце, а затем обменивается позициями с любой картой.
Код заключается в следующем:
Кода -копия выглядит следующим образом:
Функция shuffle_insert (m) // shush // Оптимизированная версия метода вставки карты может быть доказана математической индукцией, что этот шаффл является равномерным.
{
// каждый раз генерирует самую большую карту и обменивает позиции со случайной картой
var arr = new Array (m);
arr [0] = 0;
для (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
возврат Arr;
}
Хорошо, все коды следующие. Заинтересованные студенты могут попробовать их на своей машине, чтобы увидеть, является ли их соответствующая эффективность выполнения и является ли конечный результат теоретически случайным.
Кода -копия выглядит следующим образом:
<html>
<голова>
<meta http-equiv = "content-type" content = "text/html; charset = gb2312">
<title> JK: javaScript Shuffling Algorithm </title>
</head>
<тело>
<script type = "text/javascript">
Функция shuffle_pick_1 (m) // метод рисования карты Shush //
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Нарисуйте по одной карте за раз и поместите ее в другую кучу. Поскольку вам необходимо извлечь элементы из массива и вытащить все последующие элементы вперед один за другим, это трудоемкое.
var arr2 = new Array ();
for (var i = m; i> 0; i--) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr.splice (rnd, 1);
}
возврат ARR2;
}
Функция shuffle_pick (m) // shut // Метод рисования карт для оптимизации карты
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// Нарисуйте по одной карте за раз и поместите ее в другую кучу. Поместите последнюю карту с невыполненностью на открытое сиденье.
var arr2 = new Array ();
for (var i = m; i> 0;) {
var rnd = math.floor (math.random ()*i);
arr2.push (arr [rnd]);
arr [rnd] = arr [-i];
}
возврат ARR2;
}
Функция shuffle_swap (m) // метод изменения карты shush //
{
// генерировать карты M.
var arr = new Array (m);
для (var i = 0; i <m; i ++) {
arr [i] = i;
}
// i-th-карта используется для изменения сидений, и вы можете изменить ее на один раунд
для (var i = 0; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1)),
temp = arr [rnd];
arr [rnd] = arr [i];
arr [i] = temp;
}
возврат Arr;
}
Функция shuffle_insert_1 (m) // shunt // Метод вставки карты
{
// Каждый раз самая большая карта генерируется и вставляется перед случайной картой. Поскольку вам нужно вставить элементы в массив и сжать все последующие элементы обратно один за другим, это требует много времени.
var arr = [0];
для (var i = 1; i <m; i ++) {
arr.splice (math.floor (math.random ()*(i+1)), 0, i);
}
возврат Arr;
}
Функция shuffle_insert (m) // shush // Оптимизированная версия метода вставки карты может быть доказана математической индукцией, что этот шаффл является равномерным.
{
// каждый раз генерирует самую большую карту и обменивает позиции со случайной картой
var arr = new Array (m);
arr [0] = 0;
для (var i = 1; i <m; i ++) {
var rnd = math.floor (math.random ()*(i+1));
arr [i] = arr [rnd];
arr [rnd] = i;
}
возврат Arr;
}
// предупреждение (shuffle_pick (10))
var funcs = [shuffle_pick_1, shuffle_pick, shuffle_swap, shuffle_insert_1, shuffle_insert],
FuncNames = ["Draw Card", «Оптимизация карты», «Изменение карты», «Вставка карты», «Оптимизация вставки карты»]
m = 10000,
times = [];
for (var i = 0; i <funcs.length; i ++) {
var d0 = новая дата ();
Funcs [i] (m);
funcnames [i] = (new Date () - d0) + '/t' + funcnames [i];
}
Alert (funcnames.join ('/n'));
</script>
</body>
</html>