D4mations.com

Fisher-Yates Shuffle Modern Algorithm JavaScript Programming Tutorial



Lesson Code: http://www.developphp.com/video/JavaScript/Fisher-Yates-Shuffle-Modern-Algorithm-Array-Programming-Tutorial
In this programming exercise we will demonstrate the concepts behind the Fisher-Yates Modern Shuffle algorithm because we are going to use its logic to program a shuffle method into JavaScript. Using a physical example on the table we will convey the logic behind the algorithm and discuss the concept, then we will write the logic in JavaScript programming to add an array shuffle method to JavaScript’s array object.

Original source

d4mer

, , , , , ,

49 responses to “Fisher-Yates Shuffle Modern Algorithm JavaScript Programming Tutorial”

  16. Thank you very much, the first time I've watch this I only watch the visual representation, and then I program it my own, I made it by looping the array from the end to 1, then inside that I made another loop, so it is nested loop, every time I loop it the end array will be replace inside the nested array with the random place of the array… But this method is more efficient and less code, It is really hard for me to understand, It takes me almost 2 days, dreaming about this problem, T_T but now I get it..

  33. The prototype method is a good idea but for some people, they may get confused by it as I know from experience of tying to demonstrate to people in a web developer forum I frequent.

    I have used a different method of shuffling and one that uses a random number that is 0 to 'nth' where the random selects the array element, in my routine I remove the element and put it in to a results array, the routine runs for as many elements in the array, the result is very compact code and like most forums, people go on about performance, which would have been relevant 20 years ago but pose no issues with todays computers.

    —————————————————————————-
    Array.prototype.shuffle = function(){
    var s = [];
    while( this.length ) s.push( this.splice( -(~~(Math.random()*this.length)|0),1) );
    return s;
    }
    testarray = ["some","data","is","here","so","we","can","shuffle","items","randomly"].shuffle();
    —————————————————————————-

    IMHO it is much faster to pull a set of elements out of an array by a random method than swapping, in the method I posted, your using a new array to store the results sequentially and the original array is reducing and the range of randoms gets lower as it would in the moving a pointer, the efficiency arguments and claims by some people are IMHO unfounded and when you examine the different methods, they are essentially doing the same thing. I have even weighted the random function to output a negative integer to pull from the end of the array like in the Fisher Yates demo you just gave.

    The output will produce something like [randomly, items, so, shuffle, we, some, can, here, is, data] and [we, so, randomly, can, here, data, some, shuffle, is, items] as an output. If your really paranoid that the sort is not random enough, you can run the shuffle twice or more times if you like…

Leave a Reply