У меня есть такой массив:

var arr1 = ["a", "b", "c", "d"];

Как я могу рандомизировать / перемешать это?

Де-факто беспристрастным алгоритмом тасования является тасовка Фишера-Йейтса (он же Кнут).

Смотрите 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];
shuffle(arr);
console.log(arr);

Еще немного информации об используемом алгоритме .

Вот JavaScript-реализация Durstenfeld shuffle , оптимизированной версии Fisher-Yates:

/* Randomize array 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]];
    }
}

Предупреждение!
Использование этого алгоритма не рекомендуется , потому что он неэффективен и сильно смещен ; смотрите комментарии. Его оставляют здесь для дальнейшего использования, потому что идея не такая уж редкая.

[1,2,3,4,5,6].sort(function() {
  return .5 - Math.random();
});

Можно (или нужно) использовать его как прототип из 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;
}

Вы можете сделать это легко с картой и сортировать:

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)

1. Мы помещаем каждый элемент в массив в объект, и даем ему случайный ключ сортировки
2. Сортируем используя случайный ключ
3. Мы распаковываем, чтобы получить оригинальные объекты

Вы можете перетасовать полиморфные массивы, и сортировка так же случайна, как и Math.random, что достаточно для большинства целей.

Поскольку элементы сортируются по согласованным ключам, которые не восстанавливаются на каждой итерации, и каждое сравнение извлекается из одного и того же распределения, любая неслучайность в распределении Math.random исключается.

скорость

Временная сложность составляет O (N log N), так же, как быстрая сортировка. Пространственная сложность O (N). Это не так эффективно, как случай Фишера-Йейтса, но, на мой взгляд, код значительно короче и более функциональный. Если у вас большой массив, вы обязательно должны использовать Фишера Йетса. Если у вас есть небольшой массив с несколькими сотнями элементов, вы можете сделать это.

Используйте библиотеку 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();

NEW!

Более короткий и, вероятно, * более быстрый алгоритм тасования Фишера-Йейтса

1. он использует пока ---
2. поразрядно к полу (числа до 10 десятичных цифр (32 бита))
3. удалены ненужные затворы и прочее

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
 }
}

Редактировать: этот ответ неверный

Смотрите комментарии и https://stackoverflow.com/a/18650169/28234 . Это оставлено здесь для справки, потому что идея не редка.

Очень простой способ для небольших массивов заключается в следующем:

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>

Надежный, Эффективный, Короткий

Некоторые решения на этой странице не являются надежными (они только частично рандомизируют массив). Другие решения значительно менее эффективны. С помощью testShuffleArrayFun(см. Ниже) мы можем проверить функции перемешивания массива на надежность и производительность. Следующие решения: надежные, эффективные и короткие (с использованием синтаксиса ES6)

[Сравнительные тесты проводились с использованием testShuffleArrayFunдругих решений в Google Chrome]

Перестановка массива на месте

    function getShuffledArr (array){
        for (var i = array.length - 1; i > 0; i--) {
            var rand = Math.floor(Math.random() * (i + 1));
            [array[i], array[rand]] = [array[rand], array[i]]
        }
    }

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
    };

Тест надежности и производительности

Как вы можете видеть на этой странице, в прошлом здесь предлагались неверные решения. Я написал и использовал следующую функцию для тестирования любых чистых (без побочных эффектов) функций рандомизации массива.

    function testShuffleArrayFun(getShuffledArrayFun){
        const arr = [0,1,2,3,4,5,6,7,8,9]

        var 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 (var i=0 ; i<n ; i++){
            //   We'll call getShuffledArrayFun n times. 
            //   And for each iteration, we'll increment the counter. 
            var 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]
        )
    }

Добавление к @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
};

Редактировать: этот ответ неверный

См. Https://stackoverflow.com/a/18650169/28234 . Это оставлено здесь для справки, потому что идея не редка.

//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 случайное число, которое может быть положительным или отрицательным, поэтому функция сортировки меняет порядок элементов случайным образом.

С 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();

Я нашел этот вариант в ответах «удалено автором» на дубликат этого вопроса. В отличие от некоторых других ответов, которые уже имеют много голосов, это:

1. На самом деле случайный
2. Не на месте (отсюда и shuffledназвание shuffle)
3. Здесь уже нет нескольких вариантов

Вот jsfiddle, показывающий это в использовании .

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;
};

arr1.sort(() => Math.random() - 0.5);

Вы можете сделать это легко с:

// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);

Пожалуйста, ссылки на JavaScript Сортировка массивов

Рекурсивное решение:

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));
};

Фишер-Йейтс перемешивает в 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);
  }
}

Прежде всего, посмотрите здесь для большого визуального сравнения различных методов сортировки в 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).

функция тасования, которая не меняет исходный массив

Обновление : здесь я предлагаю относительно простой (не с точки зрения сложности ) и короткий алгоритм, который отлично подойдет для небольших массивов, но он определенно будет стоить намного дороже, чем классический алгоритм Дюрстенфельда , когда вы имеете дело с огромными массивами. Вы можете найти Дурстенфельд в одном из лучших ответов на этот вопрос.

Оригинальный ответ:

Если вы не хотите, чтобы функция 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;
}

Вот самый легкий ,

function shuffle(array) {
  return array.sort(() => Math.random() - 0.5);
}

для дальнейшего примера, вы можете проверить это здесь

Еще одна реализация Фишера-Йейтса, использующая строгий режим:

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;
}

Все остальные ответы основаны на 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));

Современное короткое встроенное решение с использованием функций ES6:

['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);

(для образовательных целей)

Простая модификация ответа 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;
};

Несмотря на то, что есть ряд реализаций, которые уже были рекомендованы, но я чувствую, что мы можем сделать это короче и проще, используя цикл 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)

Просто чтобы иметь палец в пироге. Здесь я представляю рекурсивную реализацию Fisher Yates shuffle (я думаю). Это дает равномерную случайность.

Примечание. ~~(Оператор двойной тильды) на самом деле ведет себя как Math.floor()для положительных действительных чисел. Это просто короткий путь.

var shuffle = a => a.length ? a.splice(~~(Math.random()*a.length),1).concat(shuffle(a))
                            : a;

console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));

Изменить: приведенный выше код O (n ^ 2) из-за использования, .splice()но мы можем устранить сращивания и перетасовки в O (n) трюк подкачки.

var shuffle = (a, l = a.length, r = ~~(Math.random()*l)) => l ? ([a[r],a[l-1]] = [a[l-1],a[r]], shuffle(a, l-1))
                                                              : a;

var arr = Array.from({length:3000}, (_,i) => i);
console.time("shuffle");
shuffle(arr);
console.timeEnd("shuffle");

Проблема в том, что JS не может работать с большими рекурсиями. В этом конкретном случае размер вашего массива ограничен примерно 3000 ~ 7000 в зависимости от вашего браузера и некоторых неизвестных фактов.

Рандомизировать массив

 var arr = ['apple','cat','Adam','123','Zorro','petunia']; 
 var n = arr.length; var tempArr = [];

 for ( var i = 0; i < n-1; i++ ) {

    // The following line removes one random element from arr 
     // and pushes it onto tempArr 
     tempArr.push(arr.splice(Math.floor(Math.random()*arr.length),1)[0]);
 }

 // Push the remaining item onto tempArr 
 tempArr.push(arr[0]); 
 arr=tempArr; 

самая короткая 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;
}

С теоретической точки зрения самый элегантный способ сделать это, по моему скромному мнению, это получить одно случайное число в диапазоне от 0 до n! -1 и вычислить отображение один к одному {0, 1, …, n!-1}для всех перестановок (0, 1, 2, …, n-1). Пока вы можете использовать (псевдо) генератор случайных чисел, достаточно надежный для получения такого числа без какого-либо существенного смещения, у вас будет достаточно информации для достижения того, что вы хотите, без необходимости использования нескольких других случайных чисел.

При вычислении с плавающими числами двойной точности IEEE754 вы можете ожидать, что ваш генератор случайных чисел предоставит около 15 десятичных знаков. Поскольку у вас 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 элементов, вы можете смело считать, что смещения не будет абсолютно.