Как рандомизировать (перетасовать) массив JavaScript?
У меня есть такой массив:
var arr1 = ["a", "b", "c", "d"];
Как я могу рандомизировать/перетасовать его?
Ответы
Ответ 1
Де-факто несмещенный алгоритм тасования - это переключение Fisher-Yates (aka Knuth).
См. https://github.com/coolaj86/knuth-shuffle
Вы можете увидеть отличную визуализацию здесь (и исходный пост связанный к этому)
function shuffle(array) {
var currentIndex = array.length, temporaryValue, randomIndex;
// While there remain elements to shuffle...
while (0 !== currentIndex) {
// Pick a remaining element...
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// And swap it with the current element.
temporaryValue = array[currentIndex];
array[currentIndex] = array[randomIndex];
array[randomIndex] = temporaryValue;
}
return array;
}
// Used like so
var arr = [2, 11, 37, 42];
arr = shuffle(arr);
console.log(arr);
Ответ 2
Вот JavaScript-реализация Durstenfeld shuffle, оптимизированной для компьютера версии Fisher-Yates:
/**
* Randomize array element order in-place.
* Using Durstenfeld shuffle algorithm.
*/
function shuffleArray(array) {
for (var i = array.length - 1; i > 0; i--) {
var j = Math.floor(Math.random() * (i + 1));
var temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Алгоритм Фишера-Йейтса работает, выбирая один случайный элемент для каждого исходного элемента массива, а затем исключая его из следующего розыгрыша. Так же, как случайный выбор из колоды карт.
Это исключение делается умным способом (изобретенным Дурстенфельдом для использования компьютерами) путем замены выбранного элемента текущим элементом, а затем выбора следующего случайного элемента из остатка. Для достижения оптимальной эффективности цикл выполняется в обратном направлении, так что случайный выбор упрощается (он всегда может начинаться с 0) и пропускает последний элемент, поскольку других вариантов больше нет.
Время выполнения этого алгоритма O (n). Обратите внимание, что перемешивание выполняется на месте. Поэтому, если вы не хотите изменять исходный массив, сначала сделайте его копию с помощью .slice(0).
Обновление до ES6/ECMAScript 2015
Новый ES6 позволяет нам назначать две переменные одновременно. Это особенно удобно, когда мы хотим поменять местами значения двух переменных, поскольку мы можем сделать это в одной строке кода. Вот сокращенная форма той же функции, использующей эту функцию.
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
Ответ 3
[изменение сообщества: этот ответ неверен; см. комментарии. Его оставляют здесь для дальнейшего использования, потому что идея не так редка.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
Ответ 4
Можно (или должен) использовать его в качестве protoype из массива:
От ChristopheD:
Array.prototype.shuffle = function() {
var i = this.length, j, temp;
if ( i == 0 ) return this;
while ( --i ) {
j = Math.floor( Math.random() * ( i + 1 ) );
temp = this[i];
this[i] = this[j];
this[j] = temp;
}
return this;
}
Ответ 5
Используйте библиотеку underscore.js. Метод _.shuffle() хорош для этого случая.
Ниже приведен пример с помощью метода:
var _ = require("underscore");
var arr = [1,2,3,4,5,6];
// Testing _.shuffle
var testShuffle = function () {
var indexOne = 0;
var stObj = {
'0': 0,
'1': 1,
'2': 2,
'3': 3,
'4': 4,
'5': 5
};
for (var i = 0; i < 1000; i++) {
arr = _.shuffle(arr);
indexOne = _.indexOf(arr, 1);
stObj[indexOne] ++;
}
console.log(stObj);
};
testShuffle();
Ответ 6
Вы можете сделать это легко с помощью карты и сортировки:
let unshuffled = ['hello', 'a', 't', 'q', 1, 2, 3, {cats: true}]
let shuffled = unshuffled
.map((a) => ({sort: Math.random(), value: a}))
.sort((a, b) => a.sort - b.sort)
.map((a) => a.value)
- Мы помещаем каждый элемент в массив в объект и предоставляем ему случайный ключ сортировки
- Мы сортируем случайный ключ
- Мы удаляем исходные объекты
Вы можете перетасовать полиморфные массивы, и сортировка такая же случайная, как Math.random, что достаточно хорошо для большинства целей.
Поскольку элементы сортируются по отношению к непротиворечивым ключам, которые не восстанавливаются на каждой итерации, и каждое сравнение вытягивается из одного и того же дистрибутива, любая неслучайность в распределении Math.random отменяется.
Ответ 7
NEW!
Короче & вероятно, быстрее алгоритм Shuffle Fisher-Yates
- он использует while ---
- побитовое слово (цифры до десяти десятичных цифр (32 бит))
- удалены ненужные замыкания & другие вещи
function fy (a, b, c, d) {//массив, заполнитель, местозаполнитель, заполнитель
с = a.length; при этом (с) Ь = Math.random() * (- с + 1) | 0, д = а [с], а [с] = а [Ь], а [Ь] = d
}
Код>
размер скрипта (с именем функции fy как): 90bytes
DEMO
http://jsfiddle.net/vvpoma8w/
* быстрее, вероятно, во всех браузерах, кроме хром.
Если у вас есть вопросы, просто спросите.
ИЗМЕНИТЬ
да, это быстрее
ПРОИЗВОДИТЕЛЬНОСТЬ: http://jsperf.com/fyshuffle
используя верхние голосовые функции.
ИЗМЕНИТЬ
Был избыток вычислений (не нужно - c + 1) , и никто не заметил
короче (4 байта) и быстрее (проверьте это!).
function fy (a, b, c, d) {//массив, заполнитель, местозаполнитель, заполнитель
с = a.length; при этом (с) Ь = Math.random() * c-- | 0, д = а [с], а [с] = а [Ь], а [Ь] = д
}
Код>
Кэширование где-то еще var rnd = Math.random, а затем использование rnd() также немного увеличит производительность на больших массивах.
http://jsfiddle.net/vvpoma8w/2/
Читаемая версия (используйте оригинальную версию, это медленнее, vars бесполезны, например, закрытия & ";", сам код также короче... возможно, прочитайте это Как "уменьшить" код Javascript, кстати, вы не можете сжимать следующие кода в javascript minifiers, как показано выше.)
function fisherYates (array) {
var count = array.length, случайное число, темп;
while (count) { randomnumber = Math.random() * count-- | 0; temp = array [count]; array [count] = array [randomnumber]; array [randomnumber] = temp
}
}
Код>
Ответ 8
Очень простой способ для небольших массивов - это просто:
const someArray = [1, 2, 3, 4, 5];
someArray.sort(() = > Math.random() - 0,5);
Код>
Это, вероятно, не очень эффективно, но для небольших массивов это работает отлично. Вот пример, чтобы вы могли видеть, насколько он случайен (или нет), и подходит ли он вам или нет.
const resultsEl = document.querySelector('# results');
const buttonEl = document.querySelector('# trigger');
const generateArrayAndRandomize =() = > {
const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
someArray.sort(() = > Math.random() - 0,5);
return someArray;
};
const renderResultsToDom = (results, el) = > {
el.innerHTML = results.join('');
};
buttonEl.addEventListener('click',() = > renderResultsToDom (generateArrayAndRandomize(), resultsEl));
<h1> Randomize! </h1>
< button id = "trigger" > Генерировать </button>
< p id = "results" > 0 1 2 3 4 5 6 7 8 9 </p>
Ответ 9
Некоторые ответы могут быть сокращены с использованием синтаксиса ES6.
ES6 Чистый, итеративный
const getShuffledArr = arr => {
const newArr = arr.slice()
for (let i = newArr.length - 1; i > 0; i--) {
const rand = Math.floor(Math.random() * (i + 1));
[newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
}
return newArr
};
Лично я использую эту функцию, поскольку она чистая, относительно простая и, согласно моим тестам в Google Chrome, наиболее эффективна (по сравнению с другими чистыми версиями).
Перестановка массива на месте
function shuffledArr (array){
for (let i = array.length - 1; i > 0; i--) {
const rand = Math.floor(Math.random() * (i + 1));
[array[i], array[rand]] = [array[rand], array[i]]
}
}
Надежность и производительность
Как вы можете видеть на этой странице, в прошлом здесь предлагались неверные решения. Итак, имея в виду надежность и производительность, я написал следующую функцию для проверки любых чистых (без побочных эффектов) функций рандомизации массива. Я использовал его, чтобы проверить все варианты, представленные в этом ответе.
function testShuffledArrayFun(getShuffledArrayFun){
const arr = [0,1,2,3,4,5,6,7,8,9]
let countArr = arr.map(el=>{
return arr.map(
el=> 0
)
}) // For each possible position in the shuffledArr and for
// each possible value, we'll create a counter.
const t0 = performance.now()
const n = 1000000
for (let i=0 ; i<n ; i++){
// We'll call getShuffledArrayFun n times.
// And for each iteration, we'll increment the counter.
const shuffledArr = getShuffledArrayFun(arr)
shuffledArr.forEach(
(value,key)=>{countArr[key][value]++}
)
}
const t1 = performance.now()
console.log('Count Values in position')
console.table(countArr)
const frequencyArr = countArr.map( positionArr => (
positionArr.map(
count => count/n
)
))
console.log("Frequency of value in position")
console.table(frequencyArr)
console.log('total time: ${t1-t0}')
}
Другие опции
ES6 Pure, рекурсивный
const getShuffledArr = arr => {
if (arr.length === 1) {return arr};
const rand = Math.floor(Math.random() * arr.length);
return [arr[rand], ...getShuffledArr(arr.filter((_, i) => i != rand))];
};
ES6 Pure с использованием array.map
function getShuffledArr (arr){
return [...arr].map( (_, i, arrCopy) => {
var rand = i + ( Math.floor( Math.random() * (arrCopy.length - i) ) );
[arrCopy[rand], arrCopy[i]] = [arrCopy[i], arrCopy[rand]]
return arrCopy[i]
})
}
ES6 Pure с использованием array.reduce
function getShuffledArr (arr){
return arr.reduce(
(newArr, _, i) => {
var rand = i + ( Math.floor( Math.random() * (newArr.length - i) ) );
[newArr[rand], newArr[i]] = [newArr[i], newArr[rand]]
return newArr
}, [...arr]
)
}
Typescript - тип для функции рандомизации чистого массива
Вы можете использовать любой из следующих.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Ответ 10
Добавление к @Laurens Holsts ответа. Это сжатие на 50%.
function shuffleArray(d) {
for (var c = d.length - 1; c > 0; c--) {
var b = Math.floor(Math.random() * (c + 1));
var a = d[c];
d[c] = d[b];
d[b] = a;
}
return d
};
Ответ 11
//one line solution
shuffle = (array) => array.sort(() => Math.random() - 0.5);
//Demo
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);
https://javascript.info/task/shuffle
Math.random() - 0.5 - это случайное число, которое может быть положительным или отрицательно, поэтому функция сортировки переупорядочивает элементы случайным образом.
Ответ 12
С ES2015 вы можете использовать этот:
Array.prototype.shuffle = function() {
let m = this.length, i;
while (m) {
i = (Math.random() * m--) >>> 0;
[this[m], this[i]] = [this[i], this[m]]
}
return this;
}
Использование:
[1, 2, 3, 4, 5, 6, 7].shuffle();
Ответ 13
var shuffle = function(array) {
temp = [];
originalLength = array.length;
for (var i = 0; i < originalLength; i++) {
temp.push(array.splice(Math.floor(Math.random()*array.length),1));
}
return temp;
};
Ответ 14
Я нашел этот вариант, болтающийся в ответах "удалил автор" в дубликате этого вопроса. В отличие от некоторых других ответов, у которых уже есть много опросов, это:
- Фактически случайный
- Не на месте (отсюда
shuffled имя, а не shuffle) - Не существует здесь с несколькими вариантами
Здесь jsfiddle показывает его в использовании.
Array.prototype.shuffled = function() {
return this.map(function(n){ return [Math.random(), n] })
.sort().map(function(n){ return n[1] });
}
Ответ 15
Вы можете сделать это легко:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Ответ 16
Рекурсивное решение:
function shuffle(a,b){
return a.length==0?b:function(c){
return shuffle(a,(b||[]).concat(c));
}(a.splice(Math.floor(Math.random()*a.length),1));
};
Ответ 17
на основе Fisher-Yates Shuffle, вы можете попробовать это многоразовое компонент массива.
Пример:
shuffle([1, 2, 3, 4, 5]) // => [2, 4, 1, 5, 3]
Мне также нравится эта функция Lodash, которая возвращает новый массив и оставляет исходный массив неизменным:
function shuffle(array) {
var rand, index = -1,
length = array.length,
result = Array(length);
while (++index < length) {
rand = Math.floor(Math.random() * (index + 1));
result[index] = result[rand];
result[rand] = array[index];
}
return result;
}
(Правильное раскрытие: я нахожусь в команде CoCycles.)
Ответ 18
функция перетасовки, которая не изменяет исходный массив
Обновление: здесь я предлагаю относительно простую (а не сложную перспективу) и короткий алгоритм, который будет прекрасно работать с малогабаритными массивами, но это определенно будет стоить намного дороже, чем классический алгоритм Дурстенфельда, когда вы имеете дело с огромными массивами. Вы можете найти Durstenfeld в одном из лучших ответов на этот вопрос.
Оригинальный ответ:
Если вы не хотите, чтобы ваша функция перетасовки мутировала исходный массив, вы можете скопировать ее в локальную переменную, а затем сделать остальную с простой логикой перетасовки.
function shuffle(array) {
var result = [], source = array.concat([]);
while (source.length) {
let index = Math.floor(Math.random() * source.length);
result.push(source[index]);
source.splice(index, 1);
}
return result;
}
Логика перестановки: выберите случайный индекс, затем добавьте соответствующий элемент в массив результатов и удалите его из копии исходного массива. Повторите это действие до тех пор, пока исходный массив не станет пустым.
И если вы действительно хотите это коротко, вот как далеко я могу получить:
function shuffle(array) {
var result = [], source = array.concat([]);
while (source.length) {
let index = Math.floor(Math.random() * source.length);
result.push(source.splice(index, 1)[0]);
}
return result;
}
Ответ 19
Прежде всего, посмотрите здесь для отличного визуального сравнения различных методов сортировки в javascript.
Во-вторых, если вы быстро посмотрите на ссылку выше, вы обнаружите, что сортировка random order, по-видимому, работает относительно хорошо по сравнению с другими методами, будучи чрезвычайно простой и быстрой для реализации, как показано ниже:
function shuffle(array) {
var random = array.map(Math.random);
array.sort(function(a, b) {
return random[array.indexOf(a)] - random[array.indexOf(b)];
});
}
Изменить: как указано в @gregers, функция сравнения вызывается со значениями, а не с индексами, поэтому вам нужно использовать indexOf. Обратите внимание, что это изменение делает код менее подходящим для больших массивов, поскольку indexOf работает в O (n) времени.
Ответ 20
Fisher-Yates перетасовать в javascript. Я размещаю это здесь, потому что использование двух служебных функций (swap и randInt) разъясняет алгоритм по сравнению с другими ответами здесь.
function swap(arr, i, j) {
// swaps two elements of an array in place
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function randInt(max) {
// returns random integer between 0 and max-1 inclusive.
return Math.floor(Math.random()*max);
}
function shuffle(arr) {
// For each slot in the array (starting at the end),
// pick an element randomly from the unplaced elements and
// place it in the slot, exchanging places with the
// element in the slot.
for(var slot = arr.length - 1; slot > 0; slot--){
var element = randInt(slot+1);
swap(arr, element, slot);
}
}
Ответ 21
еще одна реализация Fisher-Yates, используя строгий режим:
function shuffleArray(a) {
"use strict";
var i, t, j;
for (i = a.length - 1; i > 0; i -= 1) {
t = a[i];
j = Math.floor(Math.random() * (i + 1));
a[i] = a[j];
a[j] = t;
}
return a;
}
Ответ 22
Простая модификация ответа CoolAJ86, которая не изменяет исходный массив:
/**
* Returns a new array whose contents are a shuffled copy of the original array.
* @param {Array} The items to shuffle.
* /questions/12346/how-to-randomize-shuffle-a-javascript-array/86720#86720
* https://stackoverflow.com/a/44071316/1673761
*/
const shuffle = (array) => {
let currentIndex = array.length;
let temporaryValue;
let randomIndex;
const newArray = array.slice();
// While there remains elements to shuffle...
while (currentIndex) {
randomIndex = Math.floor(Math.random() * currentIndex);
currentIndex -= 1;
// Swap it with the current element.
temporaryValue = newArray[currentIndex];
newArray[currentIndex] = newArray[randomIndex];
newArray[randomIndex] = temporaryValue;
}
return newArray;
};
Ответ 23
Просто чтобы пальцем в пирог. Здесь я представляю рекурсивную реализацию Shisher Fisher Yates (я думаю). Это дает равномерную случайность.
Примечание: ~~ (оператор двойной тильды) на самом деле ведет себя как Math.floor() для положительных действительных чисел. Это короткий отрезок.
var shuffle = a = > a.length? a.splice(~~ (Math.random() * a.length), 1).concat(перетасовка (а))
: a;
console.log(JSON.stringify(перетасовка ([0,1,2,3,4,5,6,7,8,9])));код>
Ответ 24
Все остальные ответы основаны на Math.random(), который быстро, но не подходит для рандомизации на основе криптографического уровня.
В приведенном ниже коде используется известный алгоритм Fisher-Yates при использовании Web Cryptography API для криптографического уровня рандомизации.
var d = [1,2,3,4,5,6,7,8,9,10];
function shuffle(a) {
var x, t, r = new Uint32Array(1);
for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {
crypto.getRandomValues(r);
x = Math.floor(r / 65536 / 65536 * m) + i;
t = a [i], a [i] = a [x], a [x] = t;
}
return a;
}
console.log(shuffle(d));
Ответ 25
Современное короткое встроенное решение с использованием функций ES6:
['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);
(для образовательных целей)
Ответ 26
Несмотря на то, что есть ряд реализаций, которые уже были рекомендованы, но я чувствую, что мы можем сделать это короче и проще, используя цикл forEach, поэтому нам не нужно беспокоиться о расчете длины массива, а также мы можем безопасно избежать использования временной переменной.
var myArr = ["a", "b", "c", "d"];
myArr.forEach((val, key) => {
randomIndex = Math.ceil(Math.random()*(key + 1));
myArr[key] = myArr[randomIndex];
myArr[randomIndex] = val;
});
// see the values
console.log('Shuffled Array: ', myArr)
Ответ 27
кратчайшая функция arrayShuffle
function arrayShuffle(o) {
for(var j, x, i = o.length; i; j = parseInt(Math.random() * i), x = o[--i], o[i] = o[j], o[j] = x);
return o;
}
Ответ 28
С теоретической точки зрения самый элегантный способ сделать это, по моему скромному мнению, состоит в том, чтобы получить одно случайное число между 0 и n! -1 и вычислить сопоставление от одного до одного от {0, 1, …, n!-1} до все перестановки (0, 1, 2, …, n-1). До тех пор, пока вы можете использовать (псевдо) случайный генератор, достаточно надежный для получения такого числа без какого-либо значительного смещения, у вас есть достаточно информации для достижения того, чего вы хотите, не требуя нескольких других случайных чисел.
При вычислении чисел с плавающей запятой с двойной точностью IEEE754 вы можете ожидать, что ваш случайный генератор будет содержать около десяти десятичных знаков. Поскольку у вас есть 15!= 1 307 674 368 000 (с 13 цифрами), вы можете использовать следующие функции с массивами, содержащими до 15 элементов, и предположить, что не будет значительного смещения с массивами, содержащими до 14 элементов. Если вы работаете с проблемой фиксированного размера, требующей многократно вычислить эту операцию в случайном порядке, вы можете попробовать следующий код, который может быть быстрее, чем другие коды, поскольку он использует Math.random только один раз (он включает в себя несколько операций копирования).
Следующая функция не будет использоваться, но я даю ее в любом случае; он возвращает индекс данной перестановки (0, 1, 2, …, n-1) в соответствии с одним сопоставлением, используемым в этом сообщении (наиболее естественным при перечислении перестановок); он предназначен для работы с 16 элементами:
function permIndex(p) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
var tail = [];
var i;
if (p.length == 0) return 0;
for(i=1;i<(p.length);i++) {
if (p[i] > p[0]) tail.push(p[i]-1);
else tail.push(p[i]);
}
return p[0] * fact[p.length-1] + permIndex(tail);
}
Взаимная предыдущая функция (необходимая для вашего собственного вопроса) ниже; он предназначен для работы с 16 элементами; он возвращает перестановку порядка n из (0, 1, 2, …, s-1):
function permNth(n, s) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000];
var i, j;
var p = [];
var q = [];
for(i=0;i<s;i++) p.push(i);
for(i=s-1; i>=0; i--) {
j = Math.floor(n / fact[i]);
n -= j*fact[i];
q.push(p[j]);
for(;j<i;j++) p[j]=p[j+1];
}
return q;
}
Теперь вы хотите просто:
function shuffle(p) {
var fact = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600, 6227020800, 87178291200, 1307674368000, 20922789888000];
return permNth(Math.floor(Math.random()*fact[p.length]), p.length).map(
function(i) { return p[i]; });
}
Он должен работать до 16 элементов с небольшим теоретическим уклоном (хотя и с незаметной с практической точки зрения); его можно рассматривать как полностью пригодное для использования 15 элементов; с массивами, содержащими менее 14 элементов, вы можете смело считать, что не будет абсолютно никакого смещения.
Ответ 29
Достаточно забавно, что не было никакого неизменяющего рекурсивного ответа:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("What?",JSON.stringify(arr))
if(currentIndex===0){
return arr;
}
const randomIndex = Math.floor(Math.random() * currentIndex);
const swap = arr[currentIndex];
arr[currentIndex] = arr[randomIndex];
arr[randomIndex] = swap;
return recur(
arr,
currentIndex - 1
);
}
return recur(arr.map(x=>x),arr.length-1);
};
var arr = [1,2,3,4,5,[6]];
console.log(shuffle(arr));
console.log(arr);
Ответ 30
Рандомизировать массив, используя array.splice()
function shuffleArray(array) {
var temp = [];
var len=array.length;
while(len){
temp.push(array.splice(Math.floor(Math.random()*array.length),1)[0]);
len--;
}
return temp;
}
//console.log("Here >>> "+shuffleArray([4,2,3,5,8,1,0]));
демо
