#721 enhancement
ronin-15560 (at lighthouseapp)

Add shuffle method to Arrays

Reported by ronin-15560 (at lighthouseapp) | June 23rd, 2009 @ 04:08 PM | in After 1.7

I use the following function constantly, and suggest to add it to Prototype:

Array.prototype.shuffle = function(){ 
  return this.sortBy(Math.random); 
});

Really short and useful, imho. Core: let me know if you

Comments and changes to this ticket

  • Tobie Langel

    Tobie Langel July 21st, 2009 @ 01:15 PM

    • State changed from “new” to “enhancement”
  • T.J. Crowder

    T.J. Crowder November 16th, 2009 @ 04:50 PM

    • Assigned user cleared.

    [responsible:none bulk edit command]

  • Tisho Georgiev

    Tisho Georgiev March 1st, 2010 @ 08:25 PM

    • Tag set to section:lang
  • mhitza

    mhitza July 21st, 2010 @ 05:21 AM

    • Importance changed from “” to “High”

    I would rather propose to use the Fisher-Yates shuffle because Math.random isn't a reliable way to sort a list.

    Array.prototype.shuffle = function() {
        for(var i = this.length - 1; i > 1; i--) {
            var j = Math.floor(Math.random()*i);
            
            var swap = this[i];
            this[i]  = this[j];
            this[j]  = swap;
        }
        
        return this;
    }
    
  • mhitza

    mhitza July 21st, 2010 @ 07:49 AM

    Yeah, an off by one error in my previous code,

    Array.prototype.shuffle = function() {
        for(var i = this.length - 1; i > 0; i--) {
            var j = Math.floor(Math.random()*i);
            
            var swap = this[i];
            this[i]  = this[j];
            this[j]  = swap;
        }
        
        return this;
    }
    
  • KKI

    KKI July 26th, 2010 @ 02:31 AM

    Hi mhitza.

    It's not an equitable "shuffle".

    The last element (at index == this.length-1) has only 1 chance to be swapped.

    The second (at index == 1) element has (this.length) chances to be swapped.

    For equity, use this :

    var lngth = this.length;
    for(var i = 0; i < lngth; i++) { 
        var j = Math.floor(Math.random()*lngth);
    
  • KKI

    KKI July 26th, 2010 @ 02:35 AM

    Sorry,

    The first and second (at index == 0 and 1) elements have (this.length-1) chances to be swapped.

  • Ryan Tenney

    Ryan Tenney August 26th, 2010 @ 07:48 PM

    Forked prototype on Github, added method Enumerable#shuffle to src/lang/enumerable.js, and submitted a pull-request.

    My commit:
    http://github.com/ryantenney/prototype/commit/3bb62a06de0825735c24d...

  • Georg Tavonius

    Georg Tavonius September 1st, 2010 @ 02:03 PM

    I would recommend the following shuffle function:

    Array.prototype.shuffle = function() {

    var result = [],
        arr = this.slice(); // make sure, we don’t destroy original array
    while(arr.length) {
        result.push(arr.splice(Math.floor(Math.random()*arr.length), 1)[0]);
    }
    return result;
    
    
    
    
    }
    It has a complexity of O(n) and gives every element the chance to be at every position in the shuffled array. It also doesn't destroy the original Array.
  • Ryan Tenney

    Ryan Tenney September 2nd, 2010 @ 03:34 AM

    Thanks to the new Pull Request features on GitHub, the URL for my pull request is http://github.com/sstephenson/prototype/pull/6

    What I have implemented is an "inside-out" variation of a Fisher-Yates (Knuth) shuffle, which efficiently shuffles the contents of the original array into a new array, without first needing to clone the array, and without modifying the original array in any way.

      /* Array.prototype.shuffle = */ function shuffle() {
        var shuffled = [], rand;
        this.each(function(value, index) {
          if (index == 0) {
            shuffled[0] = value;
          } else {
            rand = Math.floor(Math.random() * (index + 1));
            shuffled[index] = shuffled[rand];
            shuffled[rand] = value;
          }
        });
        return shuffled;
      }
    

    (I attempted to adhere to convention and thus used this.each(...) to iterate over the array.)

    This implementation is consistent with a pseudocode reference 'implementation' of the Fisher-Yates shuffle.

       Initialize array a of n elements to a randomly shuffled copy of source, both 0-based:
       a[0] ← source[0]
       for i from 1 to n - 1 do
           j ← random integer with 0 ≤ j ≤ i
           a[i] ← a[j]
           a[j] ← source[i]
    

    As the Fisher-Yates shuffle is perhaps the best known, and most widely implemented (not to mention theoretically sound) shuffle algorithm, I would argue very strongly against attempting other approach.

  • Georg Tavonius

    Georg Tavonius September 2nd, 2010 @ 04:03 PM

    I now read all about the Fisher-Yates shuffle and officially discard my proposal in favor of Fisher-Yates.

  • ronin-15560 (at lighthouseapp)

    ronin-15560 (at lighthouseapp) September 2nd, 2010 @ 04:06 PM

    • Milestone changed from 1.7 to After 1.7

    Guys, this doesn't need to be the best randomizing method ever. Some simple and elegant is sufficient for 99% of use cases.

    I strongly suggest to use the original implementation I've posted and document that if you need something beyond that, use the Fisher-Yates shuffle or some other method.

  • Ryan Tenney

    Ryan Tenney September 2nd, 2010 @ 04:25 PM

    I would disagree. Anything less than the best shuffling method fails to deliver on what its name promises.

    A good article I read recently on this topic concerns Microsoft's implementation of a shuffle algorithm and its inability to generate an unbiased outcome. The code used in this case was:

    function RandomSort (a,b)
    {
        return (0.5 - Math.random());
    }
    

    More recently Microsoft fixed their implementation, by switching to a Fisher-Yates Shuffle.

    function ArrayShuffle(a)
    {
        var d, c, b=a.length;
        while(b)
        {
            c=Math.floor(Math.random()*b);
            d=a[--b];
            a[b]=a[c];
            a[c]=d
        }
    }
    
  • Ryan Tenney

    Ryan Tenney September 2nd, 2010 @ 04:28 PM

    As a note, the second article I linked to in my last post (here), the author notes:

    In the end I don’t think it is reasonable to expect every programmer to be memorize the Fisher-Yates algorithm. These things belong in our standard libraries.

  • John-David Dalton
  • ronin-15560 (at lighthouseapp)

    ronin-15560 (at lighthouseapp) September 2nd, 2010 @ 04:46 PM

    I don't think performance is that interesting for shuffling arrays. How often do you do that? I'd rather not add 8 additional lines of code.

  • John-David Dalton

    John-David Dalton September 2nd, 2010 @ 05:00 PM

    You can tweak the lines of code down to 4 lines more or so.
    Considering you can't predict the use case for shuffle() and the dramatic performance hit of your approach in a majority of browsers I can't recommend your solution.

  • ronin-15560 (at lighthouseapp)

    ronin-15560 (at lighthouseapp) September 2nd, 2010 @ 05:00 PM

    Btw, did you actually run statistics comparing those functions? The problem in the MS article is that it uses a method that expects a comparison between two values, whereas sortBy, a Prototype.js-provided function expects just one value.

    That means that .sortBy(Math.random) should yield the same statistics as fisher-Yates does.

  • John-David Dalton

    John-David Dalton September 2nd, 2010 @ 05:05 PM

    http://www.merlyn.demon.co.uk/js-shufl.htm#UaE scroll down to A Nasty Shuffle. (Array#sort is the weakest link)

  • Ryan Tenney

    Ryan Tenney September 2nd, 2010 @ 06:05 PM

    Thomas, I'm sorry, you're absolutely right that arr.sortBy(Math.random) is entirely different from arr.sort(Math.random). I overlooked the fact that sortBy is implemented in Prototype very differently from the native sort. The quality of the shuffle using arr.sortBy(Math.random) does not appear to be substantially different from using a FY Shuffle.

    As far as performance goes, were the difference merely 10%, yes, perhaps that would be an acceptable tradeoff for using a 1-liner and keeping the solution as simple as possible. In actuality, the FY shuffle is substantially faster (5x or better) across the board (John - thanks for the JSPerf test case.)

Please Sign in or create a free account to add a new ticket.

With your very own profile, you can contribute to projects, track your activity, watch tickets, receive and update tickets through your email and much more.

New-ticket Create new ticket

Create your profile

Help contribute to this project by taking a few moments to create your personal profile. Create your profile »

The Prototype JavaScript library.

Shared Ticket Bins

Pages