JavaScript: Shuffling Array Elements

"Shuffle" is a bit different than "random" in JavaScript (or any other programming language). If we use only Math.random(), there will be same occurrences. Which is not really "shuffling".

For example

We have an array with ["a", "b", "c", "d"] elements.
We can loop through the array while creating a random index to copy the randomly chosen element to a new array.
If we do not delete the copied element from the original array, there will be some not-wanted things going on there on the output.
There'll be duplicates and there are elements which weren't picked.
Output example: ["c", "a", "a", "d"], or ["d", "b", "b", "b"], or ["a", "a", "c", "a"], etc.

To solve that,
we need to trim the old array reference after one element gets picked by the "random index".
Let me explain it with words before you see the coding.

Example
We have the same array as above: ["a", "b", "c", "d"]. And we wanna shuffle the elements.

Create a buffer-array to store the original array (clone it), so that nothing will happen to the original one.
Then create an empty array to store the shuffled elements.
Loop through the buffer-array to randomly pick an element from it, then place that chosen element to the empty array. Then delete/remove that particular element from the buffer-array.
For instance, from that ["a", "b", "c", "d"], we generate random index of 1, which means, the element "b" is chosen. Then the empty array will consist of ["b"] and the buffer-array will be ["a", "c", "d"].
And after that, the random index is also 1, no problem, because the buffer-array is different now. So, the chosen element (with index 1) from ["a", "c", "d"] will be "c". Now, the "empty array" consists of ["b", "c"] and the buffer-array is ["a", "d"].
And so on.

As you can see in that looping sequence, the buffer-array length will decrease until it's empty, and the empty array length will increase and it will have the shuffled elements.

That highly sophisticated explanation in JavaScript coding
You can copy-paste this to your JavaScript console and hit enter/return to see the output.

function shuffle(old_array) {
    var buffer_array = old_array.slice(), //clone the old_array
        length = buffer_array.length, //initial length
        new_array = [], //for storing new shuffled array
        i = 0, //for looping
        index; //for random index

    //looping starts
    for(i; i < length; i++) {
        //random index based on buffer_array length (dynamic length)
        index = Math.floor(Math.random() * buffer_array.length);
        
        //place the randomly picked element to new_array
        new_array.push(buffer_array[index]);
        
        //remove the picked element from buffer_array
        //the buffer_array length will be decreased by 1
        buffer_array.splice(index, 1);
    }
    return new_array; //output: new shuffled array
}
/*\
|*|**************************|*|
|*| using the function above |*|
|*|**************************|*|
\*/
var array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"], //input array
    shuffled_array = shuffle(array); //shuffled array
    
//original array
console.log(array);

//shuffled array output
console.log(shuffled_array);

The original array, with the variable array, will be left intact.

That shuffle function above can be cascaded, like:

var four_shuffles = shuffle(shuffle(shuffle(shuffle(original_array))));

To shuffle the original array four times.

Using do-while or while or forEach instead of for
You can compact/shorten this as you need to. These examples below are the "readable" versions.

//Using [do-while]
function shuffle(old_array) {
    var buffer_array = old_array.slice(),
        length = buffer_array.length, //initial length
        len, //dynamic length
        new_array = [],
        i = 0,
        index;

    do {
        len = buffer_array.length; //dynamic length
        index = Math.floor(Math.random() * len);            
        new_array.push(buffer_array[index]);
        buffer_array.splice(index, 1);
        i++;
    } while (i < length);
    
    return new_array;
}

//**************************************************
//Using just [while]
function shuffle(old_array) {
    var buffer_array = old_array.slice(),
        length = buffer_array.length,
        len,
        new_array = [],
        i = 0,
        index;

    while (i < length) {
        len = buffer_array.length;
        index = Math.floor(Math.random() * len);            
        new_array.push(buffer_array[index]);
        buffer_array.splice(index, 1);
        i++;
    }
    
    return new_array;
}

//**************************************************
//Using just [forEach]
function shuffle(old_array) {
    var buffer_array = old_array.slice(),                
        new_array = [],
        index;
    // use the *old_array* as the looping reference
    old_array.forEach(function () {
        index = Math.floor(Math.random() * buffer_array.length);            
        new_array.push(buffer_array[index]);
        buffer_array.splice(index, 1);
    });
    
    return new_array;
}

As you can see on those four snippets above, I'm not trying to shorten the methods, so that you can read it.
Also, those examples above are fast for plenty of elements.

Anywho, the last looping method is using forEach. It's introduced in ES5 (ECMAScript 5). It's like each in jQuery.
More information about forEach

Documentation at Mozilla Developer Network
Documentation at Microsoft Developer Network

Monkey Raptor

Monkey Raptor

Wednesday, March 18, 2015

JavaScript: Shuffling Array Elements

No comments

Post a Comment