Как перемешать массив
Напишите функцию 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;Применение такого алгоритма гарантирует, что ни один элемент не останется на прежнем месте.
�� Как перемешать массив в Python: простые способы и примеры
Перемешивание массива важный аспект программирования, особенно при работе с данными. В этой статье мы рассмотрим различные способы, которые позволят вам перемешать массив в языке программирования Python.
1. Использование функции random.shuffle()
Модуль random в Python предоставляет функцию shuffle(), которая перемешивает элементы массива в случайном порядке.
import random array = [1, 2, 3, 4, 5] random.shuffle(array) print(array)
Результат выполнения кода:
[5, 2, 4, 3, 1]
2. Использование функции numpy.random.shuffle()
Если вы работаете с массивами, используя библиотеку NumPy, вы можете воспользоваться функцией shuffle() из модуля numpy.random. Она работает аналогично функции random.shuffle().
import numpy as np array = np.array([1, 2, 3, 4, 5]) np.random.shuffle(array) print(array)
Результат выполнения кода:
[3 5 1 4 2]
3. Использование функции sorted() с random()
Еще один способ перемешать массив — использовать функцию sorted() с использованием функции random() из модуля random. Этот метод создает новый массив со случайным порядком элементов.
import random array = [1, 2, 3, 4, 5] shuffled_array = sorted(array, key=lambda x: random.random()) print(shuffled_array)
Результат выполнения кода:
[2, 3, 4, 1, 5]
4. Использование функции numpy.random.permutation()
В библиотеке NumPy также есть функция permutation(), которая возвращает новый перемешанный массив.
import numpy as np array = np.array([1, 2, 3, 4, 5]) shuffled_array = np.random.permutation(array) print(shuffled_array)
Результат выполнения кода:
[2 5 3 1 4]
Заключение
Теперь у вас есть несколько способов перемешивания массива в языке программирования Python. Вы можете выбрать подходящий метод в зависимости от своих потребностей и предпочтений.
Как перемешать элементы массива 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] Самый оптимальный способ для перемешивания элементов массива — это алгоритм тасования Фишера — Йетса, он рассмотрен выше.