Как рандомизировать (перемешать) массив JavaScript?

Question

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

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

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

Answer 1

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

Answer 2

Просто чтобы иметь палец в пироге.Здесь я представляю рекурсивную реализацию 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])));

Answer 3

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

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

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

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

Достаточно забавно, что не было ни одного неискажающего рекурсивного ответа:

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

Answer 9

// Create a places array which holds the index for each item in the
// passed in array.
// 
// Then return a new array by randomly selecting items from the
// passed in array by referencing the places array item. Removing that
// places item each time though.
function shuffle(array) {
    let places = array.map((item, index) => index);
    return array.map((item, index, array) => {
      const random_index = Math.floor(Math.random() * places.length);
      const places_value = places[random_index];
      places.splice(random_index, 1);
      return array[places_value];
    })
}

Answer 10

Array.prototype.shuffle=function(){
   var len = this.length,temp,i
   while(len){
    i=Math.random()*len-- |0;
    temp=this[len],this[len]=this[i],this[i]=temp;
   }
   return this;
}