Как перемешать (случайно переставить) элементы в массиве?
Есть данные, записанные в массив или генерируемые на лету. Как можно получить их случайную перестановку в массиве или другом контейнере? Например: как можно получить случайную перестановку чисел от 1 до n в массиве/списке?
Отслеживать
задан 24 июл 2016 в 14:47
206k 28 28 золотых знаков 291 291 серебряный знак 526 526 бронзовых знаков
3 ответа 3
Сортировка: Сброс на вариант по умолчанию
Если у вас уже есть набор данных (массив или List ), скорее всего вам нужно перемешивание его «на месте». Для этого подойдёт алгоритм из 3.4.2P из TAOCP, известный также как Fisher–Yates shuffle.
Пусть ваши данные находятся в массиве T[] data . Пусть random — экземпляр типа Random *. Тогда для перемешивания подходит следующий код:
for (int i = data.Length - 1; i >= 1; i--) < int j = random.Next(i + 1); // обменять значения data[j] и data[i] var temp = data[j]; data[j] = data[i]; data[i] = temp; >Код очевидным образом адаптируется для случая List .
Для случая, когда вам нужна не перетасовка на месте, а заполнение данными из другого источника, или данные генерируются на ходу (например, вы хотите получить перестановку чисел 1. n), можно воспользоваться немного модифицированным алгоритмом.
Если количество данных известно заранее (пусть это будет n ), делаем так:
data = new T[n]; for (int i = 0; i
Здесь generate(i) — выражение, которое даёт следующий, i -ый член исходной последовательности. Например, если данные поступают из массива source , то generate(i) — это просто source[i] . Если вы перемешиваете числа от 1 до n , это просто i + 1 , и т. д.
Для случая, когда количество элементов не известно заранее (например, из произвольного IEnumerable ), подойдёт следующая модификация. Наш целевой контейнер должен быть List , чтобы его можно было динамически увеличивать.
data = new List(); foreach (var s in source) < int j = random.Next(data.Length + 1); if (j == data.Count) < data.Add(s); >else < data.Add(data[j]); data[j] = s; >> Код основан на цитированной статье из Википедии.
*Если вы пользуетесь .NET Framework (но не .NET Core), не стоит создавать новый экземпляр Random каждый раз при выполнении этого алгоритма: это даёт большие шансы, что два раза подряд сгенерированная перестановка будет фактически одинаковой. Если ваша программа однопоточная, лучше всего создать единственный статический экземпляр Random в начале программы, и использовать его.
Для .NET Core этой проблемы нет, создавайте экземпляры Random , где вам удобнее.
Как перемешать элементы массива js
Правильный способ — использовать алгоритм тасования Фишера — Йетса:
< let m = array.length, t, i; // Пока есть элементы для перемешивания while (m) < // Взять оставшийся элемент i = Math.floor(Math.random() * m--); // И поменять его местами с текущим элементом t = array[m]; array[m] = array[i]; array[i] = t; >return array; >
23 октября 2022
Есть еще один способ для перемешивания элементов массива. Он не очень удачный и является не очень эффективным, поэтому рассмотрим его только в качестве примера.
Напишем собственную функцию для перетасовки элементов массива.
const shuffle = (coll) => return Array(coll.length).fill(null) // возвращаем новый массив с такой же длиной и заполняем его null .map((_, i) => [Math.random(), i]) // на каждой итерации возвращаем новый массив, в котором рандомное число и индекс элемента .sort(([a], [b]) => a - b) // сортируем по рандомному элементу в порядке возрастания .map(([, i]) => coll[i]) // возвращаем элемент по индексу, который был отсортирован >; console.log(shuffle(numbers)); // => [10, 5, 3, 7, 2, 9, 1, 4, 6, 8] console.log(shuffle(numbers)); // => [9, 2, 6, 1, 8, 5, 7, 10, 3, 4] console.log(shuffle(numbers)); // => [8, 7, 10, 6, 3, 2, 9, 5, 4, 1] Самый оптимальный способ для перемешивания элементов массива — это алгоритм тасования Фишера — Йетса, он рассмотрен выше.
Как перемешать элементы массива
Напишите функцию shuffle(array) , которая перемешивает (переупорядочивает случайным образом) элементы массива.
Многократные прогоны через shuffle могут привести к разным последовательностям элементов. Например:
let arr = [1, 2, 3]; shuffle(arr); // arr = [3, 2, 1] shuffle(arr); // arr = [2, 1, 3] shuffle(arr); // arr = [3, 1, 2] // . Все последовательности элементов должны иметь одинаковую вероятность. Например, [1,2,3] может быть переупорядочено как [1,2,3] или [1,3,2] , или [3,1,2] и т.д., с равной вероятностью каждого случая.
Простым решением может быть:
function shuffle(array) < array.sort(() =>Math.random() - 0.5); > let arr = [1, 2, 3]; shuffle(arr); alert(arr);Это, конечно, будет работать, потому что Math.random() — 0.5 отдаёт случайное число, которое может быть положительным или отрицательным, следовательно, функция сортировки меняет порядок элементов случайным образом.
Но поскольку метод sort не предназначен для использования в таких случаях, не все возможные варианты имеют одинаковую вероятность.
Например, рассмотрим код ниже. Он запускает shuffle 1000000 раз и считает вероятность появления для всех возможных вариантов arr :
function shuffle(array) < array.sort(() =>Math.random() - 0.5); > // подсчёт вероятности для всех возможных вариантов let count = < '123': 0, '132': 0, '213': 0, '231': 0, '321': 0, '312': 0 >; for (let i = 0; i < 1000000; i++) < let array = [1, 2, 3]; shuffle(array); count[array.join('')]++; >// показать количество всех возможных вариантов for (let key in count) < alert(`$: $`); >Результат примера (зависят от движка JS):
123: 250706 132: 124425 213: 249618 231: 124880 312: 125148 321: 125223Теперь мы отчётливо видим допущенное отклонение: 123 и 213 появляются намного чаще, чем остальные варианты.
Результаты этого кода могут варьироваться при запуске на разных движках JavaScript, но очевидно, что такой подход не надёжен.
Так почему это не работает? Если говорить простыми словами, то sort это «чёрный ящик»: мы бросаем в него массив и функцию сравнения, ожидая получить отсортированный массив. Но из-за абсолютной хаотичности сравнений чёрный ящик сходит с ума, и как именно он сходит с ума, зависит от конкретной его реализации, которая различна в разных движках JavaScript.
Есть и другие хорошие способы решить эту задачу. Например, есть отличный алгоритм под названием Тасование Фишера — Йетса. Суть заключается в том, чтобы проходить по массиву в обратном порядке и менять местами каждый элемент со случайным элементом, который находится перед ним.
function shuffle(array) < for (let i = array.length - 1; i >0; i--) < let j = Math.floor(Math.random() * (i + 1)); // случайный индекс от 0 до i // поменять элементы местами // мы используем для этого синтаксис "деструктурирующее присваивание" // подробнее о нём - в следующих главах // то же самое можно записать как: // let t = array[i]; array[i] = array[j]; array[j] = t [array[i], array[j]] = [array[j], array[i]]; >>Давайте проверим эту реализацию на том же примере:
Алгоритм перемешивания массива
Очередной раз встретилась простая, но интересная задача – в заданном массиве перемешать имеющиеся значения.
Иногда эта задача еще формулируется как заполнение массива неповторяющимися значениями в случайном порядке. Но писать алгоритм, который будет генерировать случайное число, затем проверять, не повторится ли это значение с уже заполненными элементами, нерационально. Гораздо правильней будет просто перемешать заданный массив. Тем более, что это позволит не усложнять процесс подбора допустимых значений, соблюдая уникальность каждого значения или учитывая вхождение каждого значения заданное количество раз.
В итоге, задача сводится только к перемешиванию имеющейся последовательности не зависимо от ее исходного состава и упорядоченности.
Самое простое решение было бы в цикле выполнить N операций замены двух элементов, индексы которых выбираются случайно. Величина N определяет качество такого перемешивания – чем больше замен, тем качественнее результат. Недостаток этого метода заключается в том, что некоторые элементы массива (особенно если он большой), могут остаться на своих исходных местах. Так же недостаток будет возможность многократного перемещения одного и того же элемента массива. В итоге, нерациональное увеличение количества замен, все же не ведет к 100% качественной перетасовке всех элементов.
Более качественный и в плане перемещения всех элементов, и в количестве операций перемешивания следующий алгоритм:
- выбираем случайный элемент массива;
- меняем его местами с последним элементом;
- снова выбираем случайный элемент массива, не затрагивая последний;
- меняем с предпоследним;
Рисунок: Алгоритм перемешивания массива
Таким образом, выбираем из сужающегося списка случайный элемент и ставим последним в этом списке. Для перемещения всех элементов потребуется на одно перемещение меньше, чем количество элементов в массиве.
const N = 9; // размер массива var mas : array[1..N] of Integer; i, r, h : Integer; begin Randomize; for i := N downto 2 do begin r := Random(i) + 1; // выбор случайного элемента if r <> i then begin // замена элементов h := mas[i]; mas[i] := mas[r]; mas[r] := h; end; end; end;В данном решении существует вероятность выпадения в качестве случайного элемента того, на который производится замена. Чтобы избежать бессмысленного перемещения одного элемента имеется проверка, которая исключит лишнюю замену. Однако, в таком случае, есть вероятность, что некоторые элементы массива могут остаться на своем месте.
Чтобы исключить этот недостаток, можно делать выборку случайного значения, не затрагивая крайний заменяемый элемент. Так как заранее известно, что заменяемый элемент выбран быть не может, дополнительное условие здесь не нужно.
const N = 9; // размер массива var mas : array[1..N] of Integer; i, r, h : Integer; begin Randomize; for i := N downto 2 do begin r := Random(i-1) + 1; // выбор случайного элемента // замена элементов h := mas[i]; mas[i] := mas[r]; mas[r] := h; end; end;Применение такого алгоритма гарантирует, что ни один элемент не останется на прежнем месте.