How can I shuffle an array? [duplicate]

Question

I want to shuffle an array of elements in JavaScript like these:

[0, 3, 3] -> [3, 0, 3]
[9, 3, 6, 0, 6] -> [0, 3, 6, 9, 6]
[3, 3, 6, 0, 6] -> [0, 3, 6, 3, 6]

Cytokinesis

This has been answered a number of times on stackoverflow. Check #2451454 here's another: #5086762 – Gunboat

A good resource for JavaScript Shuffle, Deal, Draw and other date and mathematic stuff. – Pharyngo

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, []) – Hamate

you can use sort() with pseudo random function, while if you have non numeric members, you can simply add numeric field. – Newtonnext

https://mcmap.net/q/45002/-how-to-randomize-shuffle-a-javascript-array – Templas

@VitaliPom Don't use sort() with random(). Sort does not expect random result and the result may not be uniform. Microsoft's browser ballot was bugged because of this. – Pane

@Hamate I wrote this one liner which does not use splice and is much faster: arr1.reduceRight((p,v,i,a)=>(v=i?~~(Math.random()*(i+1)):i, v-i?[a[v],a[i]]=[a[i],a[v]]:0, a),a); Also check out this function. – Pane

@Pane thanks! Didn't know that. Took me a while to understand what I wrote what I answered on that :) Thanks for clarifying your answer. – Newtonnext

Answer 1

Use the modern version of the Fisher–Yates shuffle algorithm:

/**
 * Shuffles array in place.
 * @param {Array} a items An array containing the items.
 */
function shuffle(a) {
    var j, x, i;
    for (i = a.length - 1; i > 0; i--) {
        j = Math.floor(Math.random() * (i + 1));
        x = a[i];
        a[i] = a[j];
        a[j] = x;
    }
    return a;
}

ES2015 (ES6) version

/**
 * Shuffles array in place. ES6 version
 * @param {Array} a items An array containing the items.
 */
function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}

Note however, that swapping variables with destructuring assignment causes significant performance loss, as of October 2017.

Use

var myArray = ['1','2','3','4','5','6','7','8','9'];
shuffle(myArray);

Implementing prototype

Using Object.defineProperty (method taken from this SO answer) we can also implement this function as a prototype method for arrays, without having it show up in loops such as for (i in arr). The following will allow you to call arr.shuffle() to shuffle the array arr:

Object.defineProperty(Array.prototype, 'shuffle', {
    value: function() {
        for (let i = this.length - 1; i > 0; i--) {
            const j = Math.floor(Math.random() * (i + 1));
            [this[i], this[j]] = [this[j], this[i]];
        }
        return this;
    }
});

Exercitation

This method (as well as the one below) both modify the original array. That's no big deal, but the example of how to call it is a bit weird. – Brassware

@Brassware +1 for pointing out that reassignment is unnecessary. In fact it's misleading, and probably should have been the FIRST thing pointed out in this comment thread. – Hydantoin

I find the ES6 swap to be slower (once I got it to work. You have to have a semicolon before a [--all the more reason to just always use them.). – Jiles

@trlkly: ES2015 variant will be slower due to the use of destructuring assignment. Hopefully engines will optimize it soon. – Morgan

Why isn't there a test of i !== j? That should save a bit of time – Scalawag

Should iterate over the array from 0 to length-1, otherwise plenty of cache-misses! – Rosebay

Why return a;? Is it simply to allow for things like shuffle(a).slice(...)? – St

What is the purpose of (i + 1) in const j = Math.floor(Math.random() * (i + 1));? Wouldn't Math.floor(Math.random() * i)); be better? – Hawthorn

Is it still true that the destructuring assignment incurs significant performance loss? – Woeful

In Node (11), this doesn't seem to be the case. In browsers, it's only marginally different, see jsperf.com/shuffle-using-destructuring-assignment – Woeful

@Regnoult j is random, so no, you can't do that. However the loop could start at i = a.length / 2 + 1. You don't have to shuffle the same items twice, indeed. – Hipped

@St yes for that purpose. @AlexisWilke if i === j, example i=j=2 then the code does [a[2], a[2]] = [a[2], a[2]]. No point. And no, you need to iterate on all elements. Think about the case random returns always 1. Your change wouldn't shuffle half of the array. – Scalawag

Sort 1, 10, 100 ? Why is this accepted ? – Terricolous

It doesn't seem semantically correct to use const for a variable that changes its value on every iteration of the loop. It's also more to type than let or var. ;-) – Pharyngo

@Pharyngo const is a perfect choice because it's block-scoped, unlike var, and it's redeclared after each interation. let would also work, but since j doesn't change it's value inside for block const is better choice – Curnin

@pauk960—regarding "it's redeclared after each interation", they aren't. Declarations of all types are only processed once on entering an execution context, see ECMA-262 §13.2.14. – Pharyngo

@Pharyngo Winky aside, 2 extra chars is a small price to pay for preventing inadvertent reassignments. const communicates intent clearly: "I declare that this variable will never be reassigned". That simplifies cognitive load for reading the code and adds expressiveness -- when you do use let (on rare occasions), it communicates "this variable will be reassigned". const by default generally makes for better-quality code, smaller functions, fewer pieces of mutable state to keep track of than let-heavy, reassignment-happy code. – Frizzle

@ggorlen—not really the right place for this discussion, however I'll reply once. The concept of constants has been around as long as mathematics and means an invariant value. In the absence of a specific keyword, they were identified using all upper case letters (e.g. Math.PI). Semantically, that is how constants remain. Using const for variables such as objects that are then assigned new properties and values is not semantically consistent, e.g. const obj = {}; obj.prop = 'value';. let, on the other hand, is semantically consistent. – Pharyngo

Answer 2

You could use the Fisher-Yates Shuffle (code adapted from this site):

function shuffle(array) {
    let counter = array.length;

    // While there are elements in the array
    while (counter > 0) {
        // Pick a random index
        let index = Math.floor(Math.random() * counter);

        // Decrease counter by 1
        counter--;

        // And swap the last element with it
        let temp = array[counter];
        array[counter] = array[index];
        array[index] = temp;
    }

    return array;
}

Ternary

Care to elaborate on what Closure Compiler does to speed this up? – Diarmit

@BrianMortenson: Pass it through and look at the resulting code. It replaces the while loop with a for loop and turns counter > 0 into 0 < counter. I'm not entirely sure what parts speed it up, but the end result is a tiny bit faster than the original. – Ternary

That first answer seems to have a bug. About once in every 15 runs I get an extra undefined column. jsfiddle.net/tomasswood/z8zm7 – Tribunate

@ThomasWood: Yep, you're right. alltom's suggestion wasn't correct. – Ternary

The ~~ is even better than | 0: index = ~~(Math.random() * counter) – Oren

@rvighne: I tested both and | 0 was marginally faster. – Ternary

there is still a bug in this answer! try: shuffle([1,2,3]); the value "1" is never on position 0 in the returned array – Heteromerous

Why you just don't use random + Array.prototype.sort? It's easier and less code than both answers. – Fatness

@Volter9: Because the distribution isn't going to be uniform. – Ternary

really interesting post by jeff atwood about this algorithm. blog.codinghorror.com/the-danger-of-naivete I wanted to know why it is implemented the way it is – Kindig

Would be better if some of the lets were replaced with const as they aren't modified at all, except for counter. – Andvari

be aware this changes the initial array, its not a functional approach. Just leaving this here for anyone that is blindely copying this (as I did lol). – Chkalov