Как рандомизировать (перемешать) массив JavaScript?
У меня есть такой массив:
var arr1 = ["a", "b", "c", "d"];
Как я могу рандомизировать / перемешать это?
74 ответа
Де-факто беспристрастным алгоритмом тасования является тасовка Фишера-Йейтса (он же Кнут).
Смотрите 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);Еще немного информации об используемом алгоритме.
Вот 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]];
}
}
Вы можете сделать это легко с картой и сортировать:
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 исключается.
[сообщество редактировать: этот ответ неверен; см комментарии Его оставляют здесь для дальнейшего использования, потому что идея не такая уж редкая.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
Используйте библиотеку 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();
Можно (или нужно) использовать его как прототип из Array:
От Кристофа:
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;
}
NEW!
Более короткий и, вероятно, * более быстрый алгоритм тасования Фишера-Йейтса
- он использует пока ---
- поразрядно к полу (числа до 10 десятичных цифр (32 бита))
- удалены ненужные затворы и прочее
function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
c=a.length;while(c)b=Math.random()*(--c+1)|0,d=a[c],a[c]=a[b],a[b]=d
}
размер скрипта (с именем fy в качестве имени функции): 90 байт
ДЕМО http://jsfiddle.net/vvpoma8w/
* быстрее, вероятно, во всех браузерах, кроме Chrome.
Если у вас есть какие-либо вопросы просто спросить.
РЕДАКТИРОВАТЬ
да, это быстрее
ВЫПОЛНЕНИЕ: http://jsperf.com/fyshuffle
используя лучшие голосующие функции.
РЕДАКТИРОВАТЬ Был расчет в избытке (не нужно --c+1), и никто не заметил
короче (4 байта) и быстрее (протестируйте!).
function fy(a,b,c,d){//array,placeholder,placeholder,placeholder
c=a.length;while(c)b=Math.random()*c--|0,d=a[c],a[c]=a[b],a[b]=d
}
Кеширование где-то еще var rnd=Math.random а затем использовать rnd() также немного увеличит производительность на больших массивах.
http://jsfiddle.net/vvpoma8w/2/
Читаемая версия (используйте оригинальную версию. Это медленнее, переменные бесполезны, как замыкания & ";", сам код также короче... возможно, прочитайте это Как "минимизировать" код Javascript, кстати, вы не можете сжать следующий код в миниатюрах javascript, как указано выше.)
function fisherYates( array ){
var count = array.length,
randomnumber,
temp;
while( count ){
randomnumber = Math.random() * count-- | 0;
temp = array[count];
array[count] = array[randomnumber];
array[randomnumber] = temp
}
}
С ES6, 2018
Некоторые ответы могут быть сокращены с помощью последней версии ES6.
Перестановка массива на месте
function shuffleArray (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]];
}
}
С ES6 мы можем назначить два значения одновременно. Это особенно удобно в строке 4 выше, где две переменные меняются местами в одной строке кода.
Оставьте оригинальный массив без изменений и верните перемешанный массив
Если вы хотите сделать более чистую функцию и оставить исходный массив без изменений, вы можете просто продублировать массив и запустить тот же алгоритм.
function getShuffledArray (arr){
let newArr = [...arr]
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;
}
Восходящий Алгоритм
Алгоритм ниже использует восходящий цикл. Это менее интуитивно, но коротко и актуально.
function getShuffledArrayAsc (arr){
let newArr = [...arr];
for (let i = 1; i < newArr.length ; i++) {
const rand = Math.floor( Math.random() * (i + 1) );
[newArr[i], newArr[rand]] = [newArr[rand], newArr[i]];
}
return newArr;
}
Проверка надежности функции рандомизации
Приведенные выше функции представили равномерное распределение при передаче в testShuffledArrayFun ниже, как в Chrome, так и в Node. Это соответствует тому, что мы ожидаем от функции рандомизации.
function testShuffledArrayFun(getShuffledArrayFun){
// Tests the reliability of the suffleArrayFunction, by callying it 1,000 times and presenting the distribution.
const testArr = [0,1,2,3,4];
const countArr = testArr.map( position => // for for each possible position in the shuffledArr, for each possible value, we'll create a counter. the counter of value 0 in position 0 will be countArr[0][0]
testArr.map( value => 0)
)
const n = 10000;
for (var i=0 ; i<n ; i++){
// We'll call getShuffledArrayFun for n times. For each shuffledArray we receive we'll increment the counterArr accordingly. At the end we'll print the distribution.
var shuffledArr = getShuffledArrayFun(testArr);
shuffledArr.forEach(
(value, key) => {countArr[key][value]++}
);
}
countArr.forEach(
(valueCountArr,key) => {
console.log(`Position ${key}:`);
valueCountArr.forEach(
(count,originalValue) => {
console.log(`The Value ${originalValue} appeared ${count*100/n}% `);
}
);
}
);
}
Очень простой способ для небольших массивов заключается в следующем:
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">Generate</button>
<p id="results">0 1 2 3 4 5 6 7 8 9</p>[1, 2, 3, 4, 5, 6, 7, 8, 9, 0].sort((x, z) => {
ren = Math.random();
if (ren == 0.5) return 0;
return ren > 0.5 ? 1 : -1
})
Bencharks
Давайте сначала посмотрим на результаты, а затем рассмотрим каждую реализацию
shuffle ниже -
соединение идет медленно
Любое решение с использованием или
shiftв цикле будет очень медленным. Что особенно заметно, когда мы увеличиваем размер массива. В наивном алгоритме мы -
- получить
randпозиция`` во входном массиве, - Добавить
t[i]к выходу -
spliceпозицияiиз массиваt
Чтобы преувеличить медленный эффект, мы продемонстрируем это на массиве из миллиона элементов. Следующий сценарий почти 30 секунд -
Добавление к @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
};
Я нашел этот вариант в ответах "удалено автором" на дубликат этого вопроса. В отличие от некоторых других ответов, которые уже имеют много голосов, это:
- На самом деле случайный
- Не на месте (отсюда
shuffledимя, а неshuffle) - Здесь уже нет нескольких вариантов
Вот jsfiddle, показывающий это в использовании.
Array.prototype.shuffled = function() {
return this.map(function(n){ return [Math.random(), n] })
.sort().map(function(n){ return n[1] });
}
function shuffle(array) {
array.sort(() => Math.random() - 0.5);
}
let arr = [1, 2, 3];
shuffle(arr);
alert(arr);
С 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();
var shuffle = function(array) {
temp = [];
for (var i = 0; i < array.length ; i++) {
temp.push(array.splice(Math.floor(Math.random()*array.length),1));
}
return temp;
};
Вот САМЫЙ ЛЕГКИЙ,
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
для дальнейшего примера вы можете проверить это здесь
Рекурсивное решение:
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));
};
Современное короткое встроенное решение с использованием функций ES6:
['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);
(для образовательных целей)
Фишер-Йейтс перемешивает в 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);
}
}
Используя алгоритм перемешивания Фишера-Йейтса и ES6:
// Original array
let array = ['a', 'b', 'c', 'd'];
// Create a copy of the original array to be randomized
let shuffle = [...array];
// Defining function returning random value from i to N
const getRandomValue = (i, N) => Math.floor(Math.random() * (N - i) + i);
// Shuffle a pair of two elements at random position j
shuffle.forEach( (elem, i, arr, j = getRandomValue(i, arr.length)) => [arr[i], arr[j]] = [arr[j], arr[i]] );
console.log(shuffle);
// ['d', 'a', 'b', 'c']
Вы можете сделать это легко с:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);Пожалуйста, ссылки на JavaScript Сортировка массивов
функция тасования, которая не меняет исходный массив
Обновление: здесь я предлагаю относительно простой (не с точки зрения сложности) и короткий алгоритм, который отлично подойдет для небольших массивов, но он определенно будет стоить намного дороже, чем классический алгоритм Дюрстенфельда, когда вы имеете дело с огромными массивами. Вы можете найти Дурстенфельд в одном из лучших ответов на этот вопрос.
Оригинальный ответ:
Если вы не хотите, чтобы функция shuffle изменяла исходный массив, вы можете скопировать его в локальную переменную, а затем сделать все остальное с помощью простой логики перемешивания.
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;
}
Прежде всего, обратите внимание на отличное визуальное сравнение различных методов сортировки в 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) время.
Все остальные ответы основаны на 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));Простая модификация ответа CoolAJ86, которая не изменяет исходный массив:
/**
* Returns a new array whose contents are a shuffled copy of the original array.
* @param {Array} The items to shuffle.
* https://stackru.com/a/2450976/1673761
* https://stackru.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;
};
Я нашел это полезным:
const shuffle = (array: any[]) => {
return array.slice().sort(() => Math.random() - 0.5);
}
console.log(shuffle([1,2,3,4,5,6,7,8,9,10]));
// Output: [4, 3, 8, 10, 1, 7, 9, 2, 6, 5]
В 2019 году мы по-прежнему перетасовываем массивы, так что вот мой подход, который мне кажется аккуратным и быстрым:
const src = [...'abcdefg'];
const shuffle = arr => arr.reduceRight((res,_,__,arr) => [...res,arr.splice(~~(Math.random()*arr.length),1)[0]],[]);
console.log(shuffle(src));.as-console-wrapper {
max-height: 100% !important;
top: 0;
}Для тех из нас, кто не очень одарен, но имеет доступ к чудесам lodash, существует такая вещь, как lodash.shuffle.