I have an array like this:
var arr1 = ["a", "b", "c", "d"];
How can I randomize / shuffle it?
This question is related to
javascript
arrays
random
shuffle
[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
})
Using sort method and Math method :
var arr = ["HORSE", "TIGER", "DOG", "CAT"];
function shuffleArray(arr){
return arr.sort( () => Math.floor(Math.random() * Math.floor(3)) - 1)
}
// every time it gives random sequence
shuffleArr(arr);
// ["DOG", "CAT", "TIGER", "HORSE"]
// ["HORSE", "TIGER", "CAT", "DOG"]
// ["TIGER", "HORSE", "CAT", "DOG"]
I have written a shuffle function on my own . The difference here is it will never repeat a value (checks in the code for this) :-
function shuffleArray(array) {
var newArray = [];
for (var i = 0; i < array.length; i++) {
newArray.push(-1);
}
for (var j = 0; j < array.length; j++) {
var id = Math.floor((Math.random() * array.length));
while (newArray[id] !== -1) {
id = Math.floor((Math.random() * array.length));
}
newArray.splice(id, 1, array[j]);
}
return newArray; }
arr1.sort(() => Math.random() - 0.5);
First of all, have a look here for a great visual comparison of different sorting methods in javascript.
Secondly, if you have a quick look at the link above you'll find that the random order
sort seems to perform relatively well compared to the other methods, while being extremely easy and fast to implement as shown below:
function shuffle(array) {
var random = array.map(Math.random);
array.sort(function(a, b) {
return random[array.indexOf(a)] - random[array.indexOf(b)];
});
}
Edit: as pointed out by @gregers, the compare function is called with values rather than indices, which is why you need to use indexOf
. Note that this change makes the code less suitable for larger arrays as indexOf
runs in O(n) time.
Here's a JavaScript implementation of the Durstenfeld shuffle, an optimized version of 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;
}
}
It picks a random element for each original array element, and excludes it from the next draw, like picking randomly from a deck of cards.
This clever exclusion swaps the picked element with the current one, then picks the next random element from the remainder, looping backwards for optimal efficiency, ensuring the random pick is simplified (it can always start at 0), and thereby skipping the final element.
Algorithm runtime is O(n)
. Note that the shuffle is done in-place so if you don't want to modify the original array, first make a copy of it with .slice(0)
.
The new ES6 allows us to assign two variables at once. This is especially handy when we want to swap the values of two variables, as we can do it in one line of code. Here is a shorter form of the same function, using this feature.
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]];
}
}
By using shuffle-array module you can shuffle your array . Here is a simple code of it .
var shuffle = require('shuffle-array'),
//collection = [1,2,3,4,5];
collection = ["a","b","c","d","e"];
shuffle(collection);
console.log(collection);
Hope this helps.
I found this variant hanging out in the "deleted by author" answers on a duplicate of this question. Unlike some of the other answers that have many upvotes already, this is:
shuffled
name rather than shuffle
)Here's a jsfiddle showing it in use.
Array.prototype.shuffled = function() {
return this.map(function(n){ return [Math.random(), n] })
.sort().map(function(n){ return n[1] });
}
Though there are a number of implementations already advised but I feel we can make it shorter and easier using forEach loop, so we don't need to worry about calculating array length and also we can safely avoid using a temporary variable.
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)
// 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];
})
}
Just to have a finger in the pie. Here i present a recursive implementation of Fisher Yates shuffle (i think). It gives uniform randomness.
Note: The ~~
(double tilde operator) is in fact behaves like Math.floor()
for positive real numbers. Just a short cut it is.
var shuffle = a => a.length ? a.splice(~~(Math.random()*a.length),1).concat(shuffle(a))_x000D_
: a;_x000D_
_x000D_
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
_x000D_
Edit: The above code is O(n^2) due to the employment of .splice()
but we can eliminate splice and shuffle in O(n) by the swap trick.
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))_x000D_
: a;_x000D_
_x000D_
var arr = Array.from({length:3000}, (_,i) => i);_x000D_
console.time("shuffle");_x000D_
shuffle(arr);_x000D_
console.timeEnd("shuffle");
_x000D_
The problem is, JS can not coop on with big recursions. In this particular case you array size is limited with like 3000~7000 depending on your browser engine and some unknown facts.
A recursive solution:
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));
};
//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
is a random number that may be positive or negative, so the sorting function reorders elements randomly.
Using Fisher-Yates shuffle algorithm and 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']
Randomly either push or unshift(add in the beginning).
['a', 'b', 'c', 'd'].reduce((acc, el) => {
Math.random() > 0.5 ? acc.push(el) : acc.unshift(el);
return acc;
}, []);
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
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
}
script size (with fy as function name): 90bytes
DEMO http://jsfiddle.net/vvpoma8w/
*faster probably on all browsers except chrome.
If you have any questions just ask.
EDIT
yes it is faster
PERFORMANCE: http://jsperf.com/fyshuffle
using the top voted functions.
EDIT There was a calculation in excess (don't need --c+1) and noone noticed
shorter(4bytes)&faster(test it!).
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
}
Caching somewhere else var rnd=Math.random
and then use rnd()
would also increase slightly the performance on big arrays.
http://jsfiddle.net/vvpoma8w/2/
Readable version (use the original version. this is slower, vars are useless, like the closures & ";", the code itself is also shorter ... maybe read this How to 'minify' Javascript code , btw you are not able to compress the following code in a javascript minifiers like the above one.)
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
}
}
Shuffle Array In place
function shuffleArr (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 Pure, Iterative
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
};
Reliability and Performance Test
Some solutions on this page aren't reliable (they only partially randomise the array). Other solutions are significantly less efficient. With testShuffleArrayFun
(see below) we can test array shuffling functions for reliability and performance.
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}`)
}
Other solutions just for fun.
ES6 Pure, Recursive
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 using 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 using 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]
)
}
Edit: This answer is incorrect
See comments and https://stackoverflow.com/a/18650169/28234. It is being left here for reference because the idea isn't rare.
A very simple way for small arrays is simply this:
const someArray = [1, 2, 3, 4, 5];
someArray.sort(() => Math.random() - 0.5);
It's probably not very efficient, but for small arrays this works just fine. Here's an example so you can see how random (or not) it is, and whether it fits your usecase or not.
const resultsEl = document.querySelector('#results');_x000D_
const buttonEl = document.querySelector('#trigger');_x000D_
_x000D_
const generateArrayAndRandomize = () => {_x000D_
const someArray = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];_x000D_
someArray.sort(() => Math.random() - 0.5);_x000D_
return someArray;_x000D_
};_x000D_
_x000D_
const renderResultsToDom = (results, el) => {_x000D_
el.innerHTML = results.join(' ');_x000D_
};_x000D_
_x000D_
buttonEl.addEventListener('click', () => renderResultsToDom(generateArrayAndRandomize(), resultsEl));
_x000D_
<h1>Randomize!</h1>_x000D_
<button id="trigger">Generate</button>_x000D_
<p id="results">0 1 2 3 4 5 6 7 8 9</p>
_x000D_
A simple modification of CoolAJ86's answer that does not modify the original array:
/**
* 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;
};
Use the underscore.js library. The method _.shuffle()
is nice for this case.
Here is an example with the method:
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();
var shuffledArray = function(inpArr){
//inpArr - is input array
var arrRand = []; //this will give shuffled array
var arrTempInd = []; // to store shuffled indexes
var max = inpArr.length;
var min = 0;
var tempInd;
var i = 0;
do{
//generate random index between range
tempInd = Math.floor(Math.random() * (max - min));
//check if index is already available in array to avoid repetition
if(arrTempInd.indexOf(tempInd)<0){
//push character at random index
arrRand[i] = inpArr[tempInd];
//push random indexes
arrTempInd.push(tempInd);
i++;
}
}
// check if random array length is equal to input array length
while(arrTempInd.length < max){
return arrRand; // this will return shuffled Array
}
};
Just pass the array to function and in return get the shuffled array
Here is the EASIEST one,
function shuffle(array) {
return array.sort(() => Math.random() - 0.5);
}
for further example, you can check it here
From a theoretical point of view, the most elegant way of doing it, in my humble opinion, is to get a single random number between 0 and n!-1 and to compute a one to one mapping from {0, 1, …, n!-1}
to all permutations of (0, 1, 2, …, n-1)
. As long as you can use a (pseudo-)random generator reliable enough for getting such a number without any significant bias, you have enough information in it for achieving what you want without needing several other random numbers.
When computing with IEEE754 double precision floating numbers, you can expect your random generator to provide about 15 decimals. Since you have 15!=1,307,674,368,000 (with 13 digits), you can use the following functions with arrays containing up to 15 elements and assume there will be no significant bias with arrays containing up to 14 elements. If you work on a fixed-size problem requiring to compute many times this shuffle operation, you may want to try the following code which may be faster than other codes since it uses Math.random
only once (it involves several copy operations however).
The following function will not be used, but I give it anyway; it returns the index of a given permutation of (0, 1, 2, …, n-1)
according to the one to one mapping used in this message (the most natural one when enumerating permuations); it is intended to work with up to 16 elements:
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);
}
The reciprocal of the previous function (required for your own question) is below; it is intended to work with up to 16 elements; it returns the permutation of order n of (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;
}
Now, what you want merely is:
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]; });
}
It should work for up to 16 elements with a little theoretical bias (though unnoticeable from a practical point of view); it can be seen as fully usable for 15 elements; with arrays containing less than 14 elements, you can safely consider there will be absolutely no bias.
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;
};
Modern short inline solution using ES6 features:
['a','b','c','d'].map(x => [Math.random(), x]).sort(([a], [b]) => a - b).map(([_, x]) => x);
(for educational purposes)
I see no one has yet given a solution that can be concatenated while not extending the Array prototype (which is a bad practice). Using the slightly lesser known reduce()
we can easily do shuffling in a way that allows for concatenation:
var randomsquares = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle).map(n => n*n);
You'd probably want to pass the second parameter []
, as otherwise if you try to do this on an empty array it'd fail:
// Both work. The second one wouldn't have worked as the one above
var randomsquares = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle, []).map(n => n*n);
var randomsquares = [].reduce(shuffle, []).map(n => n*n);
Let's define shuffle
as:
var shuffle = (rand, one, i, orig) => {
if (i !== 1) return rand; // Randomize it only once (arr.length > 1)
// You could use here other random algorithm if you wanted
for (let i = orig.length; i; i--) {
let j = Math.floor(Math.random() * i);
[orig[i - 1], orig[j]] = [orig[j], orig[i - 1]];
}
return orig;
}
You can see it in action in JSFiddle or here:
var shuffle = (all, one, i, orig) => {_x000D_
if (i !== 1) return all;_x000D_
_x000D_
// You could use here other random algorithm here_x000D_
for (let i = orig.length; i; i--) {_x000D_
let j = Math.floor(Math.random() * i);_x000D_
[orig[i - 1], orig[j]] = [orig[j], orig[i - 1]];_x000D_
}_x000D_
_x000D_
return orig;_x000D_
}_x000D_
_x000D_
for (var i = 0; i < 5; i++) {_x000D_
var randomarray = [1, 2, 3, 4, 5, 6, 7].reduce(shuffle, []);_x000D_
console.log(JSON.stringify(randomarray));_x000D_
}
_x000D_
We're still shuffling arrays in 2019, so here goes my approach, which seems to be neat and fast to me:
const src = [...'abcdefg'];
const shuffle = arr =>
[...arr].reduceRight((res,_,__,s) =>
(res.push(s.splice(0|Math.random()*s.length,1)[0]), res),[]);
console.log(shuffle(src));
_x000D_
.as-console-wrapper {min-height: 100%}
_x000D_
Randomize array using 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]));
Community says arr.sort((a, b) => 0.5 - Math.random())
isn't 100% random!
yes! I tested and recommend do not use this method!
let arr = [1, 2, 3, 4, 5, 6]
arr.sort((a, b) => 0.5 - Math.random());
But I am not sure. So I Write some code to test !...You can also Try ! If you are interested enough!
let data_base = []; _x000D_
for (let i = 1; i <= 100; i++) { // push 100 time new rendom arr to data_base!_x000D_
data_base.push(_x000D_
[1, 2, 3, 4, 5, 6].sort((a, b) => {_x000D_
return Math.random() - 0.5; // used community banned method! :-) _x000D_
})_x000D_
);_x000D_
} // console.log(data_base); // if you want to see data!_x000D_
let analysis = {};_x000D_
for (let i = 1; i <= 6; i++) {_x000D_
analysis[i] = Array(6).fill(0);_x000D_
}_x000D_
for (let num = 0; num < 6; num++) {_x000D_
for (let i = 1; i <= 100; i++) {_x000D_
let plus = data_base[i - 1][num];_x000D_
analysis[`${num + 1}`][plus-1]++;_x000D_
}_x000D_
}_x000D_
console.log(analysis); // analysed result
_x000D_
In 100 different random arrays. (my analysed result)
{ player> 1 2 3 4 5 6
'1': [ 36, 12, 17, 16, 9, 10 ],
'2': [ 15, 36, 12, 18, 7, 12 ],
'3': [ 11, 8, 22, 19, 17, 23 ],
'4': [ 9, 14, 19, 18, 22, 18 ],
'5': [ 12, 19, 15, 18, 23, 13 ],
'6': [ 17, 11, 15, 11, 22, 24 ]
}
// player 1 got > 1(36 times),2(15 times),...,6(17 times)
// ...
// ...
// player 6 got > 1(10 times),2(12 times),...,6(24 times)
As you can see It is not that much random ! soo...
do not use this method!
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {_x000D_
const recur = (arr,currentIndex)=>{_x000D_
console.log("What?",JSON.stringify(arr))_x000D_
if(currentIndex===0){_x000D_
return arr;_x000D_
}_x000D_
const randomIndex = Math.floor(Math.random() * currentIndex);_x000D_
const swap = arr[currentIndex];_x000D_
arr[currentIndex] = arr[randomIndex];_x000D_
arr[randomIndex] = swap;_x000D_
return recur(_x000D_
arr,_x000D_
currentIndex - 1_x000D_
);_x000D_
}_x000D_
return recur(arr.map(x=>x),arr.length-1);_x000D_
};_x000D_
_x000D_
var arr = [1,2,3,4,5,[6]];_x000D_
console.log(shuffle(arr));_x000D_
console.log(arr);
_x000D_
yet another implementation of Fisher-Yates, using strict mode:
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;
}
d3.js provides a built-in version of the Fisher–Yates shuffle:
console.log(d3.shuffle(["a", "b", "c", "d"]));
_x000D_
<script src="http://d3js.org/d3.v5.min.js"></script>
_x000D_
d3.shuffle(array[, lo[, hi]]) <>
Randomizes the order of the specified array using the Fisher–Yates shuffle.
You can do it easily with map and sort:
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)
You can shuffle polymorphic arrays, and the sort is as random as Math.random, which is good enough for most purposes.
Since the elements are sorted against consistent keys that are not regenerated each iteration, and each comparison pulls from the same distribution, any non-randomness in the distribution of Math.random is canceled out.
Speed
Time complexity is O(N log N), same as quick sort. Space complexity is O(N). This is not as efficient as a Fischer Yates shuffle but, in my opinion, the code is significantly shorter and more functional. If you have a large array you should certainly use Fischer Yates. If you have a small array with a few hundred items, you might do this.
You can do it easily with:
// array_x000D_
var fruits = ["Banana", "Orange", "Apple", "Mango"];_x000D_
// random_x000D_
fruits.sort(function(a, b){return 0.5 - Math.random()});_x000D_
// out_x000D_
console.log(fruits);
_x000D_
Please reference at JavaScript Sorting Arrays
Not the best implementation but it's recursive and respect immutability.
const randomizer = (array, output = []) => {
const arrayCopy = [...array];
if (arrayCopy.length > 0) {
const idx = Math.floor(Math.random() * arrayCopy.length);
const select = arrayCopy.splice(idx, 1);
output.push(select[0]);
randomizer(arrayCopy, output);
}
return output;
};
the shortest arrayShuffle
function
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;
}
I was thinking about oneliner to paste in console. All tricks with .sort
was giving wrong results, here is my implementation:
['Bob', 'Amy', 'Joy'].map((person) => `${Math.random().toFixed(10)}${person}`).sort().map((person) => person.substr(12));
But don't use it in production code, it's not optimal and works with strings only.
For those of us who are not very gifted but have access to the wonders of lodash, there is such a thing as lodash.shuffle.
I like to share one of the million ways to solve this problem =)
function shuffleArray(array = ["banana", "ovo", "salsicha", "goiaba", "chocolate"]) {
const newArray = [];
let number = Math.floor(Math.random() * array.length);
let count = 1;
newArray.push(array[number]);
while (count < array.length) {
const newNumber = Math.floor(Math.random() * array.length);
if (!newArray.includes(array[newNumber])) {
count++;
number = newNumber;
newArray.push(array[number]);
}
}
return newArray;
}
Update: Here I'm suggesting a relatively simple (not from complexity perspective) and short algorithm that will do just fine with small sized arrays, but it's definitely going to cost a lot more than the classic Durstenfeld algorithm when you deal with huge arrays. You can find the Durstenfeld in one of the top replies to this question.
Original answer:
If you don't wish your shuffle function to mutate the source array, you can copy it to a local variable, then do the rest with a simple 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;
}
Shuffling logic: pick up a random index, then add the corresponding element to the result array and delete it from the source array copy. Repeat this action until the source array gets empty.
And if you really want it short, here's how far I could get:
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;
}
Shuffle array of strings:
shuffle = (array) => {
let counter = array.length, temp, index;
while ( counter > 0 ) {
index = Math.floor( Math.random() * counter );
counter--;
temp = array[ counter ];
array[ counter ] = array[ index ];
array[ index ] = temp;
}
return array;
}
One could (or should) use it as a protoype from Array:
From 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;
}
function shuffleArray(array) {_x000D_
// Create a new array with the length of the given array in the parameters_x000D_
const newArray = array.map(() => null);_x000D_
_x000D_
// Create a new array where each index contain the index value_x000D_
const arrayReference = array.map((item, index) => index);_x000D_
_x000D_
// Iterate on the array given in the parameters_x000D_
array.forEach(randomize);_x000D_
_x000D_
return newArray;_x000D_
_x000D_
function randomize(item) {_x000D_
const randomIndex = getRandomIndex();_x000D_
_x000D_
// Replace the value in the new array_x000D_
newArray[arrayReference[randomIndex]] = item;_x000D_
_x000D_
// Remove in the array reference the index used_x000D_
arrayReference.splice(randomIndex,1);_x000D_
}_x000D_
_x000D_
// Return a number between 0 and current array reference length_x000D_
function getRandomIndex() {_x000D_
const min = 0;_x000D_
const max = arrayReference.length;_x000D_
return Math.floor(Math.random() * (max - min)) + min;_x000D_
}_x000D_
}_x000D_
_x000D_
console.log(shuffleArray([10,20,30,40,50,60,70,80,90,100]));
_x000D_
With ES2015 you can use this one:
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;
}
Usage:
[1, 2, 3, 4, 5, 6, 7].shuffle();
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;
}
Warning!
The use of this algorithm is not recommended, because it is inefficient and strongly biased; see comments. It is being left here for future reference, because the idea is not that rare.
[1,2,3,4,5,6].sort( () => .5 - Math.random() );
This https://javascript.info/array-methods#shuffle-an-array tutorial explains the differences straightforwardly.
A functional solution using Ramda.
const {map, compose, sortBy, prop} = require('ramda')
const shuffle = compose(
map(prop('v')),
sortBy(prop('i')),
map(v => ({v, i: Math.random()}))
)
shuffle([1,2,3,4,5,6,7])
bencharks
Let's first see the results then we'll look at each implementation of shuffle
below -
splice is slow
Any solution using splice
or shift
in a loop is going to be very slow. Which is especially noticeable when we increase the size of the array. In a naive algorithm we -
rand
position, i
, in the input array, t
t[i]
to the outputsplice
position i
from array t
To exaggerate the slow effect, we'll demonstrate this on an array of one million elements. The following script almost 30 seconds -
const shuffle = t =>
Array.from(sample(t, t.length))
function* sample(t, n)
{ let r = Array.from(t)
while (n > 0 && r.length)
{ const i = rand(r.length) // 1
yield r[i] // 2
r.splice(i, 1) // 3
n = n - 1
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via splice")
const result = shuffle(bigarray)
console.timeEnd("shuffle via splice")
document.body.textContent = JSON.stringify(result, null, 2)
_x000D_
body::before {
content: "1 million elements via splice";
font-weight: bold;
display: block;
}
_x000D_
pop is fast
The trick is not to splice
and instead use the super efficient pop
. To do this, in place of the typical splice
call, you -
i
t[i]
with the last element, t[t.length - 1]
t.pop()
to the resultNow we can shuffle
one million elements in less than 100 milliseconds -
const shuffle = t =>
Array.from(sample(t, t.length))
function* sample(t, n)
{ let r = Array.from(t)
while (n > 0 && r.length)
{ const i = rand(r.length) // 1
swap(r, i, r.length - 1) // 2
yield r.pop() // 3
n = n - 1
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via pop")
const result = shuffle(bigarray)
console.timeEnd("shuffle via pop")
document.body.textContent = JSON.stringify(result, null, 2)
_x000D_
body::before {
content: "1 million elements via pop";
font-weight: bold;
display: block;
}
_x000D_
even faster
The two implementations of shuffle
above produce a new output array. The input array is not modified. This is my preferred way of working however you can increase the speed even more by shuffling in place.
Below shuffle
one million elements in less than 10 milliseconds -
function shuffle (t)
{ let last = t.length
let n
while (last > 0)
{ n = rand(last)
swap(t, n, --last)
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle in place")
shuffle(bigarray)
console.timeEnd("shuffle in place")
document.body.textContent = JSON.stringify(bigarray, null, 2)
_x000D_
body::before {
content: "1 million elements in place";
font-weight: bold;
display: block;
}
_x000D_
$=(m)=>console.log(m);_x000D_
_x000D_
//----add this method to Array class _x000D_
Array.prototype.shuffle=function(){_x000D_
return this.sort(()=>.5 - Math.random());_x000D_
};_x000D_
_x000D_
$([1,65,87,45,101,33,9].shuffle());_x000D_
$([1,65,87,45,101,33,9].shuffle());_x000D_
$([1,65,87,45,101,33,9].shuffle());_x000D_
$([1,65,87,45,101,33,9].shuffle());_x000D_
$([1,65,87,45,101,33,9].shuffle());
_x000D_
Randomize array
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;
Rebuilding the entire array, one by one putting each element at a random place.
[1,2,3].reduce((a,x,i)=>{a.splice(Math.floor(Math.random()*(i+1)),0,x);return a},[])
var ia= [1,2,3];_x000D_
var it= 1000;_x000D_
var f = (a,x,i)=>{a.splice(Math.floor(Math.random()*(i+1)),0,x);return a};_x000D_
var a = new Array(it).fill(ia).map(x=>x.reduce(f,[]));_x000D_
var r = new Array(ia.length).fill(0).map((x,i)=>a.reduce((i2,x2)=>x2[i]+i2,0)/it)_x000D_
_x000D_
console.log("These values should be quite equal:",r);
_x000D_
Ronald Fisher and Frank Yates shuffle
ES2015 (ES6) release
Array.prototype.shuffle2 = function () {
this.forEach(
function (v, i, a) {
let j = Math.floor(Math.random() * (i + 1));
[a[i], a[j]] = [a[j], a[i]];
}
);
return this;
}
Jet optimized ES2015 (ES6) release
Array.prototype.shuffle3 = function () {
var m = this.length;
while (m) {
let i = Math.floor(Math.random() * m--);
[this[m], this[i]] = [this[i], this[m]];
}
return this;
}
Fisher-Yates shuffle in javascript. I'm posting this here because the use of two utility functions (swap and randInt) clarifies the algorithm compared to the other answers here.
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);
}
}
All the other answers are based on Math.random() which is fast but not suitable for cryptgraphic level randomization.
The below code is using the well known Fisher-Yates
algorithm while utilizing Web Cryptography API
for cryptographic level of randomization.
var d = [1,2,3,4,5,6,7,8,9,10];_x000D_
_x000D_
function shuffle(a) {_x000D_
var x, t, r = new Uint32Array(1);_x000D_
for (var i = 0, c = a.length - 1, m = a.length; i < c; i++, m--) {_x000D_
crypto.getRandomValues(r);_x000D_
x = Math.floor(r / 65536 / 65536 * m) + i;_x000D_
t = a [i], a [i] = a [x], a [x] = t;_x000D_
}_x000D_
_x000D_
return a;_x000D_
}_x000D_
_x000D_
console.log(shuffle(d));
_x000D_
Adding to @Laurens Holsts answer. This is 50% compressed.
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
};
This variation of Fisher-Yates is slightly more efficient because it avoids swapping an element with itself:
function shuffle(array) {
var elementsRemaining = array.length, temp, randomIndex;
while (elementsRemaining > 1) {
randomIndex = Math.floor(Math.random() * elementsRemaining--);
if (randomIndex != elementsRemaining) {
temp = array[elementsRemaining];
array[elementsRemaining] = array[randomIndex];
array[randomIndex] = temp;
}
}
return array;
}
Considering apply it to in loco or to a new immutable array, following other solutions, here is a suggested implementation:
Array.prototype.shuffle = function(local){
var a = this;
var newArray = typeof local === "boolean" && local ? this : [];
for (var i = 0, newIdx, curr, next; i < a.length; i++){
newIdx = Math.floor(Math.random()*i);
curr = a[i];
next = a[newIdx];
newArray[i] = next;
newArray[newIdx] = curr;
}
return newArray;
};
Source: Stackoverflow.com