У меня есть массив следующего вида:
var arr1 = ["a", "b", "c", "d"];
Как я могу рандомизировать / перетасовать его?
Де-факто беспристрастным алгоритмом перестановки является алгоритм Фишера-Ятса (он же Knuth) Shuffle.
См. 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, оптимизированной для компьютера версии Фишера-Ятса:
/**
* 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 позволяет нам присваивать две переменные одновременно. Это особенно удобно, когда мы хотим поменять местами значения двух переменных, так как мы можем сделать это в одной строке кода. Вот более короткая форма той же функции, использующая эту возможность.
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]];
}
}
[сообщество редактировать: этот ответ неверен; см. комментарии. Он оставлен здесь для использования в будущем, потому что идея не такая уж и редкость.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
Можно (или нужно) использовать его как прототип от Array:
От 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;
}
Использовать библиотеку Underscore.js . Метод _.перетасовать()
хороший для этого дела.
Вот пример с методом:
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();
Вы можете сделать это легко с помощью карты и сортировки:
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)
Вы можете перетасовать полиморфных решетках и сортировки случайное, как математика.Random, который вполне пригоден для большинства целей.
Поскольку элементы сортируются с последовательными ключами, которые не восстанавливаются каждой итерации, и каждое сравнение тянет из того же дистрибутива, либо неслучайности распределения математике.случайно отменил.
Новый!
*Короче & вероятно быстрее Фишер-Йейтс алгоритм перетасовки**
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
}
размер скрипта (с результатом как имя функции): 90bytes
Демо
*быстрее, наверное, на всех браузерах, кроме хрома.
Если у вас есть какие-либо вопросы просто спросить.
Редактировать
да это быстрее
Производительность: http://jsperf.com/fyshuffle
с помощью верхней голосовал функции.
Редактировать Был расчет в избытке (Дон'т нужно-с+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
}
Кэширование где-то еще ВАР рнд=математика.случайныйи потом
рнд () также будет немного увеличить производительность на больших массивах.
Читабельную версию (используйте оригинальную версию. это медленнее, Варс бесполезны, как и закрытие &ампер; на ";" Ну, сам код тоже короче ... может это читать https://stackoverflow.com/questions/1737388/how-to-minify-javascript-code/21353032#21353032 , кстати, вы не можете сжимать следующий код в JavaScript, который minifiers, как выше.)
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
}
}
Редактировать: этот ответ неправильный
Ознакомиться с комментариями и https://stackoverflow.com/a/18650169/28234. Он оставлен здесь для ознакомления, потому что идея-это'т редкие.
Очень простой способ для небольших массивов это:
const someArray = [1, 2, 3, 4, 5];
someArray.sort(() => Math.random() - 0.5);
Это'ы, наверное, не очень эффективные, но для небольших массивов это работает просто отлично. Здесь'ы пример, так что вы можете увидеть, как случайные (или нет) это, и есть ли она подходит для вашего usecase или нет.
в
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>
в
Решения можно сократить, используя синтаксис ЕС6.
Массива, перемешивание на месте
const 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]]
}
}
Чистый
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
};
Лично я использую эту функцию, как это чистое, относительно проста, и по данным моих тестов на Гугл Хром самое эффективное (по сравнению с другими чисто версий).
Надежность и тестирование производительности
Как вы можете видеть на этой странице, были ошибочные решения, предлагаемые здесь в прошлом. Следующая функция проверяет любое чистое (без побочных эффектов) случайной функции массива. Я использовал его, чтобы проверить все варианты, представленные в этом ответе.
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}`)
}
Другие ЕС6 решения, просто для удовольствия.
Чисто, Рекурсивные
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))];
};
Чисто с использованием массива.карте
const getShuffledArr = arr => [...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]
}
)
Чисто с использованием массива.уменьшить
const getShuffledArr = arr => 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]
)
Машинопись - типа для чистого массива случайной функции
type GetShuffledArr = <T>(arr:ReadonlyArray<T>) => Array<T>
//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
математика.случайный() - 0.5-это случайное число, которое может быть положительным или отрицателен, поэтому функция сортировки упорядочивает элементы случайным образом.
Добавив к @Лоренс 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
};
С 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();
Я нашел этот вариант висит в "удален по автору" и ответы на дубликат этот вопрос. В отличие от некоторых других ответов, которые уже многие голоса, это:
тасуется
имени, а не перемешать
)[Здесь's в jsfiddle показывая его в использовании][1].
Array.prototype.shuffled = function() {
return this.map(function(n){ return [Math.random(), n] })
.sort().map(function(n){ return n[1] });
}
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;
};
Вы можете сделать это легко с:
в
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
в
Пожалуйста, ссылка на массивы JavaScript сортировка
Update: здесь я'м, что свидетельствует о сравнительно простой (не от complexity точки зрения) и короткие алгоритм, который будет делать только штрафом при малых размерах массивов, но это'ы наверняка будет стоить намного больше, чем классический Durstenfeld алгоритм, когда вы имеете дело с огромными массивами. Вы можете найти Durstenfeld в одном из лучших ответов на этот вопрос.
Original ответ:
Если вы don'т wish функции перемешать, чтобы мутировать исходный массив, вы можете скопировать его на локальную переменную, а потом делать все остальное с простым shuffling logic.
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;
}
Шаркая логика: получить случайный индекс, а затем добавить соответствующий элемент в array_ _result и удалить его из source copy массива. Повторяйте это действие, пока исходный массив получает empty.
И если вы действительно хотите его короче, здесь's, как далеко я могу сделать:
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.
Во-вторых, если у вас есть быстрый взгляд по ссылке выше вы'll найти, что случайный порядок сортировки, кажется, чувствовать себя относительно хорошо по сравнению с другими методами, в то же время крайне легко и быстро реализовать, как показано ниже:
function shuffle(array) {
var random = array.map(Math.random);
array.sort(function(a, b) {
return random[array.indexOf(a)] - random[array.indexOf(b)];
});
}
Редактировать: как указал @грегерс, сравнить функция вызывается со значениями, А не индексы, который является, почему вы должны использовать помощи indexOf
. Обратите внимание, что это изменение делает код меньше, подходит для больших массивов, как помощи indexOf
работает в o(n) времени.
Фишер-Йейтс перетасовать в JavaScript. Я'м отправляю это здесь, потому что использование двух функций полезности (своп и 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);
}
}
Простая модификация CoolAJ86'ы ответ, что не изменяет исходный массив:
/**
* Returns a new array whose contents are a shuffled copy of the original array.
* @param {Array} The items to shuffle.
* https://stackoverflow.com/a/2450976/1673761
* 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;
};