How to randomize (shuffle) a JavaScript array?
I have an array like this:
var arr1 = ["a", "b", "c", "d"];
How can I randomize / shuffle it?
javascript arrays shuffle
|
show 3 more comments
I have an array like this:
var arr1 = ["a", "b", "c", "d"];
How can I randomize / shuffle it?
javascript arrays shuffle
10
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
6
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
3
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51
|
show 3 more comments
I have an array like this:
var arr1 = ["a", "b", "c", "d"];
How can I randomize / shuffle it?
javascript arrays shuffle
I have an array like this:
var arr1 = ["a", "b", "c", "d"];
How can I randomize / shuffle it?
javascript arrays shuffle
javascript arrays shuffle
edited Sep 20 '17 at 23:52
Nit
13.1k84076
13.1k84076
asked Mar 15 '10 at 22:37
Click UpvoteClick Upvote
97.1k229510689
97.1k229510689
10
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
6
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
3
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51
|
show 3 more comments
10
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
6
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
3
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51
10
10
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
6
6
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
3
3
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51
|
show 3 more comments
44 Answers
44
active
oldest
votes
1 2
next
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
See https://github.com/coolaj86/knuth-shuffle
You can see a great visualization here (and the original post linked to this)
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);
Some more info about the algorithm used.
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
The above answer skips element 0, the condition should bei--
not--i
. Also, the testif (i==0)...
is superfluous since ifi == 0
the while loop will never be entered. The call toMath.floor
can be done faster using...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.
– RobG
Jun 8 '11 at 7:21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
|
show 21 more comments
Here is a JavaScript implementation of the Durstenfeld shuffle, a computer-optimized version of 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;
}
}
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
The running time of this algorithm is O(n). Note that the shuffle is done in-place. So if you do not want to modify the original array, make a copy of it first with .slice(0)
.
Updating to ES6 / ECMAScript 2015
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]];
}
}
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
It is not required toreturn array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.
– Joel Trauger
Aug 9 '16 at 13:31
5
The implementation in this answer favors the lower end of the array. Found out the hard way.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.
– Marjan Venema
Dec 18 '16 at 20:17
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
|
show 11 more comments
[community edit: This answer is incorrect; see comments. It is being left here for future reference because the idea is not that rare.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
|
show 16 more comments
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;
}
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
@TinyGiant Actually: don't usefor...in
loops to iterate over arrays.
– Conor O'Brien
Nov 7 '15 at 3:27
|
show 2 more comments
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();
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
@frabcus: There's no point in including an entire library just to get ashuffle
function.
– Blender
Jun 8 '13 at 20:42
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
|
show 6 more comments
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
- it uses while---
- bitwise to floor (numbers up to 10 decimal digits (32bit))
- removed unecessary closures & other stuff
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
}
}
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping thefy
andshuffle prototype
, I getfy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3
– Spig
Oct 9 '14 at 18:49
|
show 20 more comments
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)
- We put each element in the array in an object, and give it a random sort key
- We sort using the random key
- We unmap to get the original objects
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.
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
|
show 4 more comments
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');
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>
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
|
show 4 more comments
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
};
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
is it efficient to dovar b =
in a loop instead of declaring b outside loop and assigning it withb =
in a loop?
– Alex K
Oct 28 '13 at 9:51
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
|
show 2 more comments
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();
4
To truncate, you should usen >>> 0
instead of~~n
. Array indices can be higher than 2³¹-1.
– Oriol
Jul 24 '16 at 3:46
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
add a comment |
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;
};
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
add a comment |
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:
- Actually random
- Not in-place (hence the
shuffled
name rather thanshuffle
) - Not already present here with multiple variants
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] });
}
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
– Daniel Martin
Jul 14 '15 at 22:58
2
You need to use.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default.sort()
comparator is lexicographic, meaning it will consider10
to be less than2
since1
is less than2
.
– 4castle
Nov 10 '17 at 14:39
|
show 1 more comment
Some of the answers could be shortened using ES6 syntax.
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
};
I personally use this function as it is pure, relatively simple, and according to my tests on Google Chrome the most efficient (compared to other pure versions).
Shuffle Array In place
function getShuffledArr (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]]
}
}
Reliability and Performance
As you can see in this page, there have been incorrect solutions offered here in the past. So, with reliability and performance in mind, I wrote the following function to test any pure (no side effects) array randomizing functions. I used it to test all the options presented in this answer.
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}`)
}
Typescript - type for a pure array randomizing function
You can use either of the following.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Other Options
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))];
};
This version is less efficient than the iterative pure version.
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]
})
}
This version is slightly less efficient than the iterative pure version.
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]
)
}
This version is slightly less efficient than the iterative pure version.
So, where is the ES6(ES2015) ?[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?
– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
add a comment |
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));
};
add a comment |
You can do it easily with:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Please reference at JavaScript Sorting Arrays
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
add a comment |
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);
}
}
add a comment |
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.
Array.prototype.sort
passes in two values asa
andb
, not the index. So this code doesn't work.
– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
add a comment |
a shuffle function that doesn't change the source array
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;
}
This is essentially the original Fisher-Yates algorithm, with yoursplice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.
– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
add a comment |
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;
}
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
add a comment |
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];
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));
add a comment |
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))
: a;
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
add a comment |
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;
};
add a comment |
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)
add a comment |
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;
}
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
add a comment |
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.
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
add a comment |
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
add a comment |
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)
add a comment |
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;
}
To truncate, you should usen >>> 0
instead ofn | 0
. Array indices can be higher than 2³¹-1.
– Oriol
Aug 11 '16 at 21:39
add a comment |
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]));
demo
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
add a comment |
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;
There shouldn't be a-1
for n as you used<
not<=
– Mohebifar
May 9 '15 at 9:04
add a comment |
1 2
next
protected by Community♦ Oct 30 '14 at 6:12
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
44 Answers
44
active
oldest
votes
44 Answers
44
active
oldest
votes
active
oldest
votes
active
oldest
votes
1 2
next
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
See https://github.com/coolaj86/knuth-shuffle
You can see a great visualization here (and the original post linked to this)
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);
Some more info about the algorithm used.
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
The above answer skips element 0, the condition should bei--
not--i
. Also, the testif (i==0)...
is superfluous since ifi == 0
the while loop will never be entered. The call toMath.floor
can be done faster using...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.
– RobG
Jun 8 '11 at 7:21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
|
show 21 more comments
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
See https://github.com/coolaj86/knuth-shuffle
You can see a great visualization here (and the original post linked to this)
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);
Some more info about the algorithm used.
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
The above answer skips element 0, the condition should bei--
not--i
. Also, the testif (i==0)...
is superfluous since ifi == 0
the while loop will never be entered. The call toMath.floor
can be done faster using...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.
– RobG
Jun 8 '11 at 7:21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
|
show 21 more comments
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
See https://github.com/coolaj86/knuth-shuffle
You can see a great visualization here (and the original post linked to this)
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);
Some more info about the algorithm used.
The de-facto unbiased shuffle algorithm is the Fisher-Yates (aka Knuth) Shuffle.
See https://github.com/coolaj86/knuth-shuffle
You can see a great visualization here (and the original post linked to this)
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);
Some more info about the algorithm used.
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);
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);
edited Mar 11 '17 at 4:18
community wiki
13 revs, 10 users 41%
CoolAJ86
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
The above answer skips element 0, the condition should bei--
not--i
. Also, the testif (i==0)...
is superfluous since ifi == 0
the while loop will never be entered. The call toMath.floor
can be done faster using...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.
– RobG
Jun 8 '11 at 7:21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
|
show 21 more comments
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
The above answer skips element 0, the condition should bei--
not--i
. Also, the testif (i==0)...
is superfluous since ifi == 0
the while loop will never be entered. The call toMath.floor
can be done faster using...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.
– RobG
Jun 8 '11 at 7:21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
4
4
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
Here's a CoffeeScript implementation of the Fisher-Yates algorithm: gist.github.com/859699
– Derek Dahmer
Mar 8 '11 at 1:57
12
12
The above answer skips element 0, the condition should be
i--
not --i
. Also, the test if (i==0)...
is superfluous since if i == 0
the while loop will never be entered. The call to Math.floor
can be done faster using ...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.– RobG
Jun 8 '11 at 7:21
The above answer skips element 0, the condition should be
i--
not --i
. Also, the test if (i==0)...
is superfluous since if i == 0
the while loop will never be entered. The call to Math.floor
can be done faster using ...| 0
. Either tempi or tempj can be removed and the value be directly assigned to myArray[i] or j as appropriate.– RobG
Jun 8 '11 at 7:21
21
21
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
@prometheus, all RNGs are pseudo-random unless connected to expensive hardware.
– Phil H
Apr 13 '12 at 14:10
33
33
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
@RobG the implementation above is functionally correct. In the Fisher-Yates algorithm, the loop isn't meant to run for the first element in the array. Check out wikipedia where there are other implementations that also skip the first element. Also check out this article which talks about why it is important for the loop not to run for the first element.
– theon
Jul 20 '12 at 12:57
24
24
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
@nikola "not random at all" is a little strong a qualification for me. I would argue that it is sufficiently random unless you're a cryptographer, in which case you're probably not using Math.Random() in the first place.
– toon81
Apr 24 '13 at 9:19
|
show 21 more comments
Here is a JavaScript implementation of the Durstenfeld shuffle, a computer-optimized version of 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;
}
}
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
The running time of this algorithm is O(n). Note that the shuffle is done in-place. So if you do not want to modify the original array, make a copy of it first with .slice(0)
.
Updating to ES6 / ECMAScript 2015
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]];
}
}
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
It is not required toreturn array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.
– Joel Trauger
Aug 9 '16 at 13:31
5
The implementation in this answer favors the lower end of the array. Found out the hard way.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.
– Marjan Venema
Dec 18 '16 at 20:17
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
|
show 11 more comments
Here is a JavaScript implementation of the Durstenfeld shuffle, a computer-optimized version of 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;
}
}
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
The running time of this algorithm is O(n). Note that the shuffle is done in-place. So if you do not want to modify the original array, make a copy of it first with .slice(0)
.
Updating to ES6 / ECMAScript 2015
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]];
}
}
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
It is not required toreturn array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.
– Joel Trauger
Aug 9 '16 at 13:31
5
The implementation in this answer favors the lower end of the array. Found out the hard way.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.
– Marjan Venema
Dec 18 '16 at 20:17
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
|
show 11 more comments
Here is a JavaScript implementation of the Durstenfeld shuffle, a computer-optimized version of 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;
}
}
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
The running time of this algorithm is O(n). Note that the shuffle is done in-place. So if you do not want to modify the original array, make a copy of it first with .slice(0)
.
Updating to ES6 / ECMAScript 2015
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]];
}
}
Here is a JavaScript implementation of the Durstenfeld shuffle, a computer-optimized version of 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;
}
}
The Fisher-Yates algorithm works by picking one random element for each original array element, and then excluding it from the next draw. Just like randomly picking from a deck of cards.
This exclusion is done in a clever way (invented by Durstenfeld for use by computers) by swapping the picked element with the current element, and then picking the next random element from the remainder. For optimal efficiency, the loop runs backwards so that the random pick is simplified (it can always start at 0), and it skips the last element because there are no other choices anymore.
The running time of this algorithm is O(n). Note that the shuffle is done in-place. So if you do not want to modify the original array, make a copy of it first with .slice(0)
.
Updating to ES6 / ECMAScript 2015
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]];
}
}
edited Nov 8 '18 at 19:18
answered Sep 28 '12 at 20:20
Laurens HolstLaurens Holst
13.3k22331
13.3k22331
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
It is not required toreturn array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.
– Joel Trauger
Aug 9 '16 at 13:31
5
The implementation in this answer favors the lower end of the array. Found out the hard way.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.
– Marjan Venema
Dec 18 '16 at 20:17
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
|
show 11 more comments
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
It is not required toreturn array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.
– Joel Trauger
Aug 9 '16 at 13:31
5
The implementation in this answer favors the lower end of the array. Found out the hard way.Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.
– Marjan Venema
Dec 18 '16 at 20:17
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
17
17
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
p.s. The same algorithm as ChristopheD’s answer, but with explanation and cleaner implementation.
– Laurens Holst
Sep 28 '12 at 20:47
10
10
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
People are attributing the wrong person for the algorithm. It's not Fisher-Yates shuffle but Durstenfeld shuffle. The true original Fisher-Yates algorithm is runs in n^2 time, not n time
– Pacerier
Oct 31 '14 at 12:32
6
6
It is not required to
return array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.– Joel Trauger
Aug 9 '16 at 13:31
It is not required to
return array
since JavaScript passes arrays by reference when used as function arguments. I assume this is to save on stack space, but it's an interesting little feature. Performing the shuffle on the array will shuffle the original array.– Joel Trauger
Aug 9 '16 at 13:31
5
5
The implementation in this answer favors the lower end of the array. Found out the hard way.
Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.– Marjan Venema
Dec 18 '16 at 20:17
The implementation in this answer favors the lower end of the array. Found out the hard way.
Math.random() should not be multiplied with the loop counter + 1, but with
array.lengt()`. See Generating random whole numbers in JavaScript in a specific range? for a very comprehensive explanation.– Marjan Venema
Dec 18 '16 at 20:17
10
10
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
@MarjanVenema Not sure if you're still watching this space, but this answer is correct, and the change you're suggesting actually introduces bias. See blog.codinghorror.com/the-danger-of-naivete for a nice writeup of this mistake.
– smarx
Mar 11 '17 at 1:44
|
show 11 more comments
[community edit: This answer is incorrect; see comments. It is being left here for future reference because the idea is not that rare.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
|
show 16 more comments
[community edit: This answer is incorrect; see comments. It is being left here for future reference because the idea is not that rare.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
|
show 16 more comments
[community edit: This answer is incorrect; see comments. It is being left here for future reference because the idea is not that rare.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
[community edit: This answer is incorrect; see comments. It is being left here for future reference because the idea is not that rare.]
[1,2,3,4,5,6].sort(function() {
return .5 - Math.random();
});
edited Sep 22 '16 at 22:19
ninjagecko
59.5k17112120
59.5k17112120
answered Sep 6 '13 at 4:55
deadrunkdeadrunk
10.3k32228
10.3k32228
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
|
show 16 more comments
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
12
12
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
i like this solution, enough to give a basic random
– Alex K
Oct 28 '13 at 9:49
116
116
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
Downvoting as this isn't really that random. I don't know why it has so many upvotes. Do not use this method. It looks pretty, but isn't completely correct. Here are results after 10,000 iterations on how many times each number in your array hits index [0] (I can give the other results too): 1 = 29.19%, 2 = 29.53%, 3 = 20.06%, 4 = 11.91%, 5 = 5.99%, 6 = 3.32%
– radtad
Nov 13 '13 at 18:35
18
18
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
It's also the least efficient of all the methods available.
– Blazemonger
Dec 17 '13 at 14:21
187
187
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
but it's very cute
– spencercooly
Apr 27 '14 at 22:26
11
11
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
The problem is that it's not deterministic, which will give wrong results (if 1 > 2 and 2 > 3, it should be given that 1 > 3, but this will not guarantee that. This will confuse the sort, and give the result commented by @radtad).
– MatsLindh
Sep 10 '14 at 14:07
|
show 16 more comments
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;
}
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
@TinyGiant Actually: don't usefor...in
loops to iterate over arrays.
– Conor O'Brien
Nov 7 '15 at 3:27
|
show 2 more comments
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;
}
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
@TinyGiant Actually: don't usefor...in
loops to iterate over arrays.
– Conor O'Brien
Nov 7 '15 at 3:27
|
show 2 more comments
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;
}
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;
}
edited May 16 '13 at 2:53
Cheeso
134k73404632
134k73404632
answered Apr 13 '12 at 13:59
concon
1,8481830
1,8481830
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
@TinyGiant Actually: don't usefor...in
loops to iterate over arrays.
– Conor O'Brien
Nov 7 '15 at 3:27
|
show 2 more comments
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
@TinyGiant Actually: don't usefor...in
loops to iterate over arrays.
– Conor O'Brien
Nov 7 '15 at 3:27
17
17
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
+1 for using prototype...
– user1589754
Sep 22 '13 at 14:22
33
33
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
Really no benefit to this, IMOHO, except possibly stomping on someone else's implementation ..
– user2864740
Sep 15 '14 at 4:17
40
40
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
One could (or should) avoid extending Native Prototypes: javascriptweblog.wordpress.com/2011/12/05/…
– Wédney Yuri
Aug 25 '15 at 23:03
7
7
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
You shouldn't do this; every single array affected by this can no longer be iterated safely using for...in. Don't extend native prototypes.
– Tiny Giant
Oct 18 '15 at 21:13
14
14
@TinyGiant Actually: don't use
for...in
loops to iterate over arrays.– Conor O'Brien
Nov 7 '15 at 3:27
@TinyGiant Actually: don't use
for...in
loops to iterate over arrays.– Conor O'Brien
Nov 7 '15 at 3:27
|
show 2 more comments
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();
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
@frabcus: There's no point in including an entire library just to get ashuffle
function.
– Blender
Jun 8 '13 at 20:42
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
|
show 6 more comments
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();
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
@frabcus: There's no point in including an entire library just to get ashuffle
function.
– Blender
Jun 8 '13 at 20:42
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
|
show 6 more comments
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();
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();
edited Oct 12 '13 at 3:05
hexacyanide
53.5k21124126
53.5k21124126
answered Mar 31 '13 at 5:29
vn_grvvn_grv
68355
68355
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
@frabcus: There's no point in including an entire library just to get ashuffle
function.
– Blender
Jun 8 '13 at 20:42
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
|
show 6 more comments
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
@frabcus: There's no point in including an entire library just to get ashuffle
function.
– Blender
Jun 8 '13 at 20:42
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
10
10
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
Great answer! Thanks. I prefer it to the other answers, as it encourages people to use libraries rather than copy and paste potentially buggy functions everywhere.
– frabcus
Apr 4 '13 at 15:07
49
49
@frabcus: There's no point in including an entire library just to get a
shuffle
function.– Blender
Jun 8 '13 at 20:42
@frabcus: There's no point in including an entire library just to get a
shuffle
function.– Blender
Jun 8 '13 at 20:42
9
9
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
I disagree with @Blender. There are many reasons to include an entire library just to get a function you need. One of them is there is less risk of a bug when you write it yourself. If it's a performance problem, then you shouldn't use it. But just because it could be a performance problem doesn't mean it will be.
– Daniel Kaplan
Jul 16 '13 at 23:04
7
7
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
@tieTYT: So why do you need the rest of the library? The Fisher-Yates shuffle is trivial to implement. You don't need a library to pick a random element out of an array (I hope), so there's no reason to use a library unless you're actually going to use more than one function from it.
– Blender
Jul 16 '13 at 23:19
15
15
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
@Blender: I gave a reason why. 1) I assure you, you can introduce a bug into any code you write, no matter how trivial it is. Why risk it? 2) Don't pre-optimize. 3) 99% of the time when you need a shuffle algo, your app isn't about writing a shuffle algo. It's about something that needs a shuffle algo. Leverage others' work. Don't think about implementation details unless you have to.
– Daniel Kaplan
Jul 17 '13 at 17:35
|
show 6 more comments
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
- it uses while---
- bitwise to floor (numbers up to 10 decimal digits (32bit))
- removed unecessary closures & other stuff
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
}
}
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping thefy
andshuffle prototype
, I getfy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3
– Spig
Oct 9 '14 at 18:49
|
show 20 more comments
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
- it uses while---
- bitwise to floor (numbers up to 10 decimal digits (32bit))
- removed unecessary closures & other stuff
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
}
}
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping thefy
andshuffle prototype
, I getfy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3
– Spig
Oct 9 '14 at 18:49
|
show 20 more comments
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
- it uses while---
- bitwise to floor (numbers up to 10 decimal digits (32bit))
- removed unecessary closures & other stuff
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
}
}
NEW!
Shorter & probably *faster Fisher-Yates shuffle algorithm
- it uses while---
- bitwise to floor (numbers up to 10 decimal digits (32bit))
- removed unecessary closures & other stuff
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
}
}
edited May 23 '17 at 12:10
Community♦
11
11
answered Sep 22 '14 at 23:21
coccococco
12.3k64068
12.3k64068
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping thefy
andshuffle prototype
, I getfy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3
– Spig
Oct 9 '14 at 18:49
|
show 20 more comments
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping thefy
andshuffle prototype
, I getfy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3
– Spig
Oct 9 '14 at 18:49
6
6
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
check out the performance ... 2x faster on most browsers... but needs more jsperf testers...
– cocco
Sep 23 '14 at 11:20
13
13
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
Yes, fine, but that's not the reason to make it unreadable.
– georg
Sep 23 '14 at 11:23
10
10
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
js is a language that accepts many shortcuts and different ways to write it.. while there are many slow readable functions in here i just like to show how it could be done in a more performant way, also saving some bytes... bitwise and shorthand is really underestimated here and the web is full of buggy and slow code.
– cocco
Sep 23 '14 at 11:29
2
2
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
And minifiers don't work properly....stackoverflow.com/a/21353032/2450730
– cocco
Sep 23 '14 at 11:33
Not a slam dunk perf increase. Swapping the
fy
and shuffle prototype
, I get fy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3– Spig
Oct 9 '14 at 18:49
Not a slam dunk perf increase. Swapping the
fy
and shuffle prototype
, I get fy
consistently at the bottom in Chrome 37 on OS X 10.9.5 (81% slower ~20k ops compared to ~100k) and Safari 7.1 it's up to ~8% slower. YMMV, but it's not always faster. jsperf.com/fyshuffle/3– Spig
Oct 9 '14 at 18:49
|
show 20 more comments
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)
- We put each element in the array in an object, and give it a random sort key
- We sort using the random key
- We unmap to get the original objects
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.
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
|
show 4 more comments
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)
- We put each element in the array in an object, and give it a random sort key
- We sort using the random key
- We unmap to get the original objects
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.
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
|
show 4 more comments
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)
- We put each element in the array in an object, and give it a random sort key
- We sort using the random key
- We unmap to get the original objects
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.
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)
- We put each element in the array in an object, and give it a random sort key
- We sort using the random key
- We unmap to get the original objects
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.
edited Jul 3 '18 at 11:39
answered Oct 3 '17 at 13:16
superluminarysuperluminary
29.2k18114130
29.2k18114130
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
|
show 4 more comments
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
3
3
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
This is short and sweet.
– Rexford
Dec 6 '17 at 8:31
1
1
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@superluminary Oops, you're right. Notice that this answer already used the same approach.
– Bergi
Dec 6 '17 at 19:42
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
@Bergi - Ah yes, you are right, although I think my implementation is slightly prettier.
– superluminary
Dec 7 '17 at 11:24
1
1
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
Very nice. This is the Schwartzian transform in js.
– Mark Grimes
Jun 29 '18 at 10:43
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
But performance is worse than FY.
– user9315861
Jul 8 '18 at 7:25
|
show 4 more comments
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');
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>
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
|
show 4 more comments
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');
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>
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
|
show 4 more comments
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');
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>
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');
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>
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>
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>
edited Mar 17 '18 at 14:01
answered Apr 5 '17 at 15:38
Kris SelbekkKris Selbekk
3,48723052
3,48723052
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
|
show 4 more comments
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Nice one, but does generate a complete random elements every time?
– Azarus
Apr 10 '17 at 20:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
Not quite sure if I understood you correctly. This approach will indeed shuffle the array in a random way (albeit pseudo-random) every time you call the sort array - it's not a stable sort, for obvious reasons.
– Kris Selbekk
Apr 11 '17 at 11:00
4
4
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
For the same reasons as explained at stackoverflow.com/a/18650169/28234 . This is much more likely to leave early elements near the start of the array.
– AlexC
Jun 23 '17 at 10:41
3
3
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
This is a great, easy one-liner for when you need to scramble an array, but don't care too much about having the results be academically provably random. Sometimes, that last few inches to perfection take more time than it's worth.
– Daniel Griscom
Nov 3 '17 at 18:48
1
1
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
It would be lovely if this worked, but it doesn't. Because of the way quick-search works, an inconsistent comparator will be likely to leave array elements close to their original position. Your array will not be scrambled.
– superluminary
Mar 14 '18 at 14:34
|
show 4 more comments
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
};
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
is it efficient to dovar b =
in a loop instead of declaring b outside loop and assigning it withb =
in a loop?
– Alex K
Oct 28 '13 at 9:51
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
|
show 2 more comments
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
};
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
is it efficient to dovar b =
in a loop instead of declaring b outside loop and assigning it withb =
in a loop?
– Alex K
Oct 28 '13 at 9:51
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
|
show 2 more comments
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
};
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
};
edited Oct 12 '13 at 3:04
hexacyanide
53.5k21124126
53.5k21124126
answered Apr 1 '13 at 21:23
KingKongFrogKingKongFrog
8,459114898
8,459114898
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
is it efficient to dovar b =
in a loop instead of declaring b outside loop and assigning it withb =
in a loop?
– Alex K
Oct 28 '13 at 9:51
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
|
show 2 more comments
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
is it efficient to dovar b =
in a loop instead of declaring b outside loop and assigning it withb =
in a loop?
– Alex K
Oct 28 '13 at 9:51
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
2
2
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
We should be encouraging people to use _.shuffle rather than pasting code from stack overflow; and, we should be discouraging people from compressing their stack overflow answers. That's what jsmin is for.
– David Jones
Apr 5 '13 at 8:28
38
38
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
@DavidJones: Why would I include an entire 4kb library just to shuffle an array?
– Blender
May 4 '13 at 19:23
1
1
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
@KingKongFrog name calling is also not conductive to a assemblage of a reasonable community.
– wheaties
May 8 '13 at 3:21
2
2
is it efficient to do
var b =
in a loop instead of declaring b outside loop and assigning it with b =
in a loop?– Alex K
Oct 28 '13 at 9:51
is it efficient to do
var b =
in a loop instead of declaring b outside loop and assigning it with b =
in a loop?– Alex K
Oct 28 '13 at 9:51
2
2
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
@Brian Won't make a difference; the hoisting happens when the source code is parsed. No probably involved.
– user2864740
Sep 15 '14 at 4:18
|
show 2 more comments
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();
4
To truncate, you should usen >>> 0
instead of~~n
. Array indices can be higher than 2³¹-1.
– Oriol
Jul 24 '16 at 3:46
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
add a comment |
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();
4
To truncate, you should usen >>> 0
instead of~~n
. Array indices can be higher than 2³¹-1.
– Oriol
Jul 24 '16 at 3:46
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
add a comment |
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();
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();
edited Jul 24 '16 at 4:26
answered Dec 20 '15 at 4:15
BrunoLMBrunoLM
59.6k66223384
59.6k66223384
4
To truncate, you should usen >>> 0
instead of~~n
. Array indices can be higher than 2³¹-1.
– Oriol
Jul 24 '16 at 3:46
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
add a comment |
4
To truncate, you should usen >>> 0
instead of~~n
. Array indices can be higher than 2³¹-1.
– Oriol
Jul 24 '16 at 3:46
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
4
4
To truncate, you should use
n >>> 0
instead of ~~n
. Array indices can be higher than 2³¹-1.– Oriol
Jul 24 '16 at 3:46
To truncate, you should use
n >>> 0
instead of ~~n
. Array indices can be higher than 2³¹-1.– Oriol
Jul 24 '16 at 3:46
1
1
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
Destructuring like this makes for such a clean implementation +1
– lukejacksonn
May 11 '17 at 12:28
add a comment |
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;
};
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
add a comment |
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;
};
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
add a comment |
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;
};
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;
};
edited Oct 12 '13 at 3:02
hexacyanide
53.5k21124126
53.5k21124126
answered Aug 9 '13 at 15:37
TopheTophe
22724
22724
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
add a comment |
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
This is obviously not as optimal as the Fisher-Yates algorithm, but would it work for technical interviews?
– davidatthepark
May 19 '16 at 22:17
1
1
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
Am I wrong or this is completely broken?
– Andrea
Feb 15 '18 at 17:15
add a comment |
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:
- Actually random
- Not in-place (hence the
shuffled
name rather thanshuffle
) - Not already present here with multiple variants
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] });
}
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
– Daniel Martin
Jul 14 '15 at 22:58
2
You need to use.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default.sort()
comparator is lexicographic, meaning it will consider10
to be less than2
since1
is less than2
.
– 4castle
Nov 10 '17 at 14:39
|
show 1 more comment
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:
- Actually random
- Not in-place (hence the
shuffled
name rather thanshuffle
) - Not already present here with multiple variants
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] });
}
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
– Daniel Martin
Jul 14 '15 at 22:58
2
You need to use.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default.sort()
comparator is lexicographic, meaning it will consider10
to be less than2
since1
is less than2
.
– 4castle
Nov 10 '17 at 14:39
|
show 1 more comment
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:
- Actually random
- Not in-place (hence the
shuffled
name rather thanshuffle
) - Not already present here with multiple variants
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] });
}
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:
- Actually random
- Not in-place (hence the
shuffled
name rather thanshuffle
) - Not already present here with multiple variants
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] });
}
edited Nov 10 '17 at 14:56
answered Jun 25 '15 at 15:25
Daniel MartinDaniel Martin
19.2k34264
19.2k34264
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
– Daniel Martin
Jul 14 '15 at 22:58
2
You need to use.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default.sort()
comparator is lexicographic, meaning it will consider10
to be less than2
since1
is less than2
.
– 4castle
Nov 10 '17 at 14:39
|
show 1 more comment
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html
– Daniel Martin
Jul 14 '15 at 22:58
2
You need to use.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default.sort()
comparator is lexicographic, meaning it will consider10
to be less than2
since1
is less than2
.
– 4castle
Nov 10 '17 at 14:39
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
(I suspect it was deleted as it is a very inefficient way to randomize the array, especially for larger arrays... whereas the accepted answer, and a number of other clones of that answer randomize in-place).
– WiredPrairie
Jul 14 '15 at 12:17
1
1
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Yeah, but given that the well-known wrong answer is still up with a bunch of votes, an inefficient but correct solution should at least be mentioned.
– Daniel Martin
Jul 14 '15 at 18:54
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
Which one is the "well-known wrong answer"?
– WiredPrairie
Jul 14 '15 at 22:49
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html– Daniel Martin
Jul 14 '15 at 22:58
[1,2,3,4,5,6].sort(function() { return .5 - Math.random(); });
- it doesn't give a random sort, and if you use it you can end up embarrassed: robweir.com/blog/2010/02/microsoft-random-browser-ballot.html– Daniel Martin
Jul 14 '15 at 22:58
2
2
You need to use
.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default .sort()
comparator is lexicographic, meaning it will consider 10
to be less than 2
since 1
is less than 2
.– 4castle
Nov 10 '17 at 14:39
You need to use
.sort(function(a,b){ return a[0] - b[0]; })
if you want the sort to compare values numerically. The default .sort()
comparator is lexicographic, meaning it will consider 10
to be less than 2
since 1
is less than 2
.– 4castle
Nov 10 '17 at 14:39
|
show 1 more comment
Some of the answers could be shortened using ES6 syntax.
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
};
I personally use this function as it is pure, relatively simple, and according to my tests on Google Chrome the most efficient (compared to other pure versions).
Shuffle Array In place
function getShuffledArr (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]]
}
}
Reliability and Performance
As you can see in this page, there have been incorrect solutions offered here in the past. So, with reliability and performance in mind, I wrote the following function to test any pure (no side effects) array randomizing functions. I used it to test all the options presented in this answer.
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}`)
}
Typescript - type for a pure array randomizing function
You can use either of the following.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Other Options
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))];
};
This version is less efficient than the iterative pure version.
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]
})
}
This version is slightly less efficient than the iterative pure version.
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]
)
}
This version is slightly less efficient than the iterative pure version.
So, where is the ES6(ES2015) ?[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?
– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
add a comment |
Some of the answers could be shortened using ES6 syntax.
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
};
I personally use this function as it is pure, relatively simple, and according to my tests on Google Chrome the most efficient (compared to other pure versions).
Shuffle Array In place
function getShuffledArr (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]]
}
}
Reliability and Performance
As you can see in this page, there have been incorrect solutions offered here in the past. So, with reliability and performance in mind, I wrote the following function to test any pure (no side effects) array randomizing functions. I used it to test all the options presented in this answer.
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}`)
}
Typescript - type for a pure array randomizing function
You can use either of the following.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Other Options
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))];
};
This version is less efficient than the iterative pure version.
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]
})
}
This version is slightly less efficient than the iterative pure version.
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]
)
}
This version is slightly less efficient than the iterative pure version.
So, where is the ES6(ES2015) ?[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?
– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
add a comment |
Some of the answers could be shortened using ES6 syntax.
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
};
I personally use this function as it is pure, relatively simple, and according to my tests on Google Chrome the most efficient (compared to other pure versions).
Shuffle Array In place
function getShuffledArr (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]]
}
}
Reliability and Performance
As you can see in this page, there have been incorrect solutions offered here in the past. So, with reliability and performance in mind, I wrote the following function to test any pure (no side effects) array randomizing functions. I used it to test all the options presented in this answer.
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}`)
}
Typescript - type for a pure array randomizing function
You can use either of the following.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Other Options
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))];
};
This version is less efficient than the iterative pure version.
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]
})
}
This version is slightly less efficient than the iterative pure version.
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]
)
}
This version is slightly less efficient than the iterative pure version.
Some of the answers could be shortened using ES6 syntax.
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
};
I personally use this function as it is pure, relatively simple, and according to my tests on Google Chrome the most efficient (compared to other pure versions).
Shuffle Array In place
function getShuffledArr (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]]
}
}
Reliability and Performance
As you can see in this page, there have been incorrect solutions offered here in the past. So, with reliability and performance in mind, I wrote the following function to test any pure (no side effects) array randomizing functions. I used it to test all the options presented in this answer.
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}`)
}
Typescript - type for a pure array randomizing function
You can use either of the following.
type GetShuffledArr= <T>(arr:Array<T>) => Array<T>
interface IGetShuffledArr{
<T>(arr:Array<T>): Array<T>
}
Other Options
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))];
};
This version is less efficient than the iterative pure version.
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]
})
}
This version is slightly less efficient than the iterative pure version.
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]
)
}
This version is slightly less efficient than the iterative pure version.
edited Jan 5 at 17:27
answered Sep 11 '17 at 18:12
Ben CarpBen Carp
946821
946821
So, where is the ES6(ES2015) ?[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?
– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
add a comment |
So, where is the ES6(ES2015) ?[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?
– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
So, where is the ES6(ES2015) ?
[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?– sheriffderek
Sep 11 '17 at 19:00
So, where is the ES6(ES2015) ?
[array[i], array[rand]]=[array[rand], array[i]]
? Maybe you can outline how that works. Why do you choose to iterate downwards?– sheriffderek
Sep 11 '17 at 19:00
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
@sheriffderek Yes, the ES6 feature I'm using is the assignment of two vars at once, which allows us to swap two vars in one line of code.
– Ben Carp
Sep 12 '17 at 2:47
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
Credit to @sheriffderek who suggested the ascending Algorithm. The ascending algorithm could be proved in induction.
– Ben Carp
Sep 15 '17 at 1:00
add a comment |
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));
};
add a comment |
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));
};
add a comment |
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));
};
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));
};
edited Mar 26 '14 at 8:40
answered Mar 26 '14 at 7:47
JulianJulian
9112
9112
add a comment |
add a comment |
You can do it easily with:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Please reference at JavaScript Sorting Arrays
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
add a comment |
You can do it easily with:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Please reference at JavaScript Sorting Arrays
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
add a comment |
You can do it easily with:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Please reference at JavaScript Sorting Arrays
You can do it easily with:
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
Please reference at JavaScript Sorting Arrays
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
// array
var fruits = ["Banana", "Orange", "Apple", "Mango"];
// random
fruits.sort(function(a, b){return 0.5 - Math.random()});
// out
console.log(fruits);
answered Jun 20 '18 at 6:59
TinhNQTinhNQ
1,0921115
1,0921115
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
add a comment |
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
This algorithm has long been proven to be defective.
– user9315861
Jul 8 '18 at 7:27
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
Please prove to me. I based on w3schools
– TinhNQ
Jul 9 '18 at 5:14
1
1
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
You could read the thread at css-tricks.com/snippets/javascript/shuffle-array, or at news.ycombinator.com/item?id=2728914. W3schools has always been, and remains, a horrible source of information.
– user9315861
Jul 9 '18 at 9:09
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
Yes this is not the right way to do it
– Alexander Mills
Jul 13 '18 at 3:50
add a comment |
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);
}
}
add a comment |
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);
}
}
add a comment |
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);
}
}
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);
}
}
edited Sep 1 '15 at 1:53
CoreDumpError
2,69332231
2,69332231
answered Aug 4 '15 at 13:50
dpatrudpatru
1,3411410
1,3411410
add a comment |
add a comment |
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.
Array.prototype.sort
passes in two values asa
andb
, not the index. So this code doesn't work.
– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
add a comment |
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.
Array.prototype.sort
passes in two values asa
andb
, not the index. So this code doesn't work.
– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
add a comment |
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.
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.
edited May 15 '16 at 15:00
answered Mar 29 '15 at 20:31
0sh0sh
1,89322235
1,89322235
Array.prototype.sort
passes in two values asa
andb
, not the index. So this code doesn't work.
– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
add a comment |
Array.prototype.sort
passes in two values asa
andb
, not the index. So this code doesn't work.
– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
Array.prototype.sort
passes in two values as a
and b
, not the index. So this code doesn't work.– gregers
Mar 29 '16 at 13:34
Array.prototype.sort
passes in two values as a
and b
, not the index. So this code doesn't work.– gregers
Mar 29 '16 at 13:34
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
@gregers you're right, I've edited the answer. Thanks.
– 0sh
May 15 '16 at 15:00
1
1
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
This is not very random. Depending on the implementation of sort, an element at the lowest array index might require more comparisons in order to get to the highest index than the element next to the highest index. This means that it is less likely for the element at the lowest index to get to the highest index.
– 1' OR 1 --
Jul 19 '16 at 0:16
add a comment |
a shuffle function that doesn't change the source array
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;
}
This is essentially the original Fisher-Yates algorithm, with yoursplice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.
– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
add a comment |
a shuffle function that doesn't change the source array
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;
}
This is essentially the original Fisher-Yates algorithm, with yoursplice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.
– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
add a comment |
a shuffle function that doesn't change the source array
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;
}
a shuffle function that doesn't change the source array
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;
}
edited Jul 20 '18 at 11:08
answered Jan 13 '18 at 23:16
Evgenia ManolovaEvgenia Manolova
1,7131820
1,7131820
This is essentially the original Fisher-Yates algorithm, with yoursplice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.
– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
add a comment |
This is essentially the original Fisher-Yates algorithm, with yoursplice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.
– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
This is essentially the original Fisher-Yates algorithm, with your
splice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.– user9315861
Jul 9 '18 at 4:49
This is essentially the original Fisher-Yates algorithm, with your
splice
being a horribly inefficient way to do what they called "striking out". If you don't want to mutate the original array, then just copy it, and then shuffle that copy in place using the much more efficient Durstenfeld variant.– user9315861
Jul 9 '18 at 4:49
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
@torazaburo, thank you for your feedback. I've updated my answer, to make it clear that I'm rather offering a nice-looking solution, than a super-scaling one
– Evgenia Manolova
Jul 20 '18 at 11:10
add a comment |
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;
}
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
add a comment |
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;
}
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
add a comment |
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;
}
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;
}
answered Oct 21 '13 at 13:20
Raphael CRaphael C
1,23011313
1,23011313
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
add a comment |
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
What value does the addition of use strict provide over the accepted answer?
– shortstuffsushi
Sep 17 '17 at 15:21
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
To learn more about strict mode and how it influences performance you can read about it here: developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…
– Raphael C
Sep 18 '17 at 17:55
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Hmm, could you point to something specific from the referenced document? Nothing in there seems to reference "improving performance," aside from a vague comment at the top about potentially making it difficult for the js engine to optimize. In this case, it's unclear to me what use strict would improve.
– shortstuffsushi
Sep 19 '17 at 15:04
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Strict mode has been around for quite some time, and there are sufficient reads out there for anyone to make their own opinion if they should always use it or not and why. Jslint for instance makes it clear enough that you should always use strict mode. Douglas Crockford has written quite an amount of articles and some great videos on why it is important to always use strict mode not only as a good practice but also how it is interpreted differently by browser js engines such as V8. I strongly advise you to Google it and make your own opinion about it.
– Raphael C
Sep 20 '17 at 15:53
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
Here is an old thread about perfs in strict mode, a bit old but still relevant: stackoverflow.com/questions/3145966/…
– Raphael C
Sep 20 '17 at 16:06
add a comment |
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];
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));
add a comment |
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];
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));
add a comment |
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];
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));
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];
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));
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));
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));
answered Sep 23 '17 at 21:33
Marcin MalinowskiMarcin Malinowski
572312
572312
add a comment |
add a comment |
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))
: a;
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
add a comment |
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))
: a;
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
add a comment |
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))
: a;
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
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))
: a;
console.log(JSON.stringify(shuffle([0,1,2,3,4,5,6,7,8,9])));
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])));
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])));
edited Mar 20 '18 at 8:08
answered Aug 30 '17 at 18:10
ReduRedu
12.7k22435
12.7k22435
add a comment |
add a comment |
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;
};
add a comment |
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;
};
add a comment |
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;
};
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;
};
edited Nov 2 '18 at 20:37
BBaysinger
1,62342458
1,62342458
answered May 19 '17 at 13:23
abumalickabumalick
41646
41646
add a comment |
add a comment |
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)
add a comment |
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)
add a comment |
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)
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)
edited Jan 6 at 22:31
answered Apr 1 '18 at 12:15
Hafizur RahmanHafizur Rahman
494413
494413
add a comment |
add a comment |
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;
}
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
add a comment |
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;
}
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
add a comment |
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;
}
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;
}
answered Oct 17 '16 at 18:13
Tusko TrushTusko Trush
378213
378213
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
add a comment |
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
Apparently you are doing Sattolo's instead of Fisher-Yates (Knuth, unbiased).
– Arthur2e5
Oct 18 '16 at 17:32
add a comment |
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.
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
add a comment |
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.
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
add a comment |
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.
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.
edited Jan 25 '18 at 7:41
answered Feb 19 '17 at 15:23
Thomas BaruchelThomas Baruchel
4,61421636
4,61421636
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
add a comment |
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
Definitely elegant!
– Gershom Maes
Jan 24 '18 at 17:34
add a comment |
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
add a comment |
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
add a comment |
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
Funny enough there was no non mutating recursive answer:
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
var shuffle = arr => {
const recur = (arr,currentIndex)=>{
console.log("fuck?",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);
edited Feb 9 '18 at 6:45
answered Feb 9 '18 at 3:32
HMRHMR
13.6k113898
13.6k113898
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
add a comment |
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
2
2
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
Maybe there wasn't because it's pretty inefficient? :-P
– Bergi
Feb 9 '18 at 4:08
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
@Bergi Correct, updated with first answer logic. Still need to copy the array for immutability. Added because this is flagged as the duplicate of a question asking for a function that takes an array and returned a shuffled array without mutating the array. Now the question actually has an answer the OP was looking for.
– HMR
Feb 9 '18 at 6:48
add a comment |
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)
add a comment |
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)
add a comment |
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)
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)
answered Mar 15 '18 at 18:14
icl7126icl7126
1,93212731
1,93212731
add a comment |
add a comment |
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;
}
To truncate, you should usen >>> 0
instead ofn | 0
. Array indices can be higher than 2³¹-1.
– Oriol
Aug 11 '16 at 21:39
add a comment |
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;
}
To truncate, you should usen >>> 0
instead ofn | 0
. Array indices can be higher than 2³¹-1.
– Oriol
Aug 11 '16 at 21:39
add a comment |
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;
}
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;
}
answered Aug 21 '14 at 6:31
user1289673user1289673
213
213
To truncate, you should usen >>> 0
instead ofn | 0
. Array indices can be higher than 2³¹-1.
– Oriol
Aug 11 '16 at 21:39
add a comment |
To truncate, you should usen >>> 0
instead ofn | 0
. Array indices can be higher than 2³¹-1.
– Oriol
Aug 11 '16 at 21:39
To truncate, you should use
n >>> 0
instead of n | 0
. Array indices can be higher than 2³¹-1.– Oriol
Aug 11 '16 at 21:39
To truncate, you should use
n >>> 0
instead of n | 0
. Array indices can be higher than 2³¹-1.– Oriol
Aug 11 '16 at 21:39
add a comment |
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]));
demo
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
add a comment |
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]));
demo
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
add a comment |
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]));
demo
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]));
demo
edited Nov 27 '14 at 15:51
answered Nov 19 '14 at 3:47
Saravanan RajaramanSaravanan Rajaraman
6281916
6281916
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
add a comment |
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
1
1
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
Essentially the same as Tophe posted more than a year before.
– trincot
Jul 20 '16 at 21:08
add a comment |
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;
There shouldn't be a-1
for n as you used<
not<=
– Mohebifar
May 9 '15 at 9:04
add a comment |
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;
There shouldn't be a-1
for n as you used<
not<=
– Mohebifar
May 9 '15 at 9:04
add a comment |
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;
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;
answered May 7 '15 at 7:51
vickisysvickisys
1,3911325
1,3911325
There shouldn't be a-1
for n as you used<
not<=
– Mohebifar
May 9 '15 at 9:04
add a comment |
There shouldn't be a-1
for n as you used<
not<=
– Mohebifar
May 9 '15 at 9:04
There shouldn't be a
-1
for n as you used <
not <=
– Mohebifar
May 9 '15 at 9:04
There shouldn't be a
-1
for n as you used <
not <=
– Mohebifar
May 9 '15 at 9:04
add a comment |
1 2
next
protected by Community♦ Oct 30 '14 at 6:12
Thank you for your interest in this question.
Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).
Would you like to answer one of these unanswered questions instead?
10
jsPerf performance comparison of several methods
– Blazemonger
Dec 17 '13 at 14:17
6
Just throwing this here that you can visualize how random a shuffle function actually is with this visualizer Mike Bostock made: bost.ocks.org/mike/shuffle/compare.html
– aug
Dec 10 '14 at 19:42
3
@Blazemonger jsPref is dead. Can you just post here which is the fastest?
– 3zzy
Sep 28 '16 at 1:06
I added an answer that can be concatenated and doesn't extend the native Array prototype.
– Francisco Presencia
Nov 12 '16 at 10:33
What about a one-liner? The returned array is shuffled. arr1.reduce((a,v)=>a.splice(Math.floor(Math.random() * a.length), 0, v) && a, )
– brunettdan
Oct 16 '17 at 19:51