dtm: (Default)
[personal profile] dtm
Because I've recently read an article on how Microsoft has egg on its face because of this, and because searching on Google for "sort a list randomly in javascript" currently shows the wrong thing to do in the top several hits, here's how to take a list in javascript and shuffle it, or sort it in a truly random order.

Also, yeah, it's been over two months since I last posted, etc.

However, this is just going to be code, and anyone who still has me in the old friends list probably doesn't need their livejournal covered with code, so it goes behind a cut...

I guess I should say first that this isn't just a problem that affects javascript - many languages have a sort function that takes an arbitrary comparison function, and it seems natural to sort in "random" order by using a comparison function that chooses its return value randomly.

Don't do this. If you do, your code won't be producing a fair shuffle. This is how Microsoft's browser choice website wound up broken.

Instead, there are two simple methods that shuffle easily and fairly: sorting by random key (random key, not random comparison function), and the Fisher-Yates shuffle. I'm doing the second because it's easier to demonstrate in javascript; the first is easier in some language like Python where it's just
list.sort(key=random.random)

So here's the code. See how short it is?
//shuffles list in-place
function shuffle(list) {
  var i, j, t;
  for (i = 1; i < list.length; i++) {
    j = Math.floor(Math.random()*(1+i));  // choose j in [0..i]
    if (j != i) {
      t = list[i];                        // swap list[i] and list[j]
      list[i] = list[j];
      list[j] = t;
    }
  }
}

Okay? Now, I don't want to see anyone else write an article or respond to a mailing list question about how to "sort a list randomly" with incorrect advice about using sort with a random comparison function. It just doesn't work.

(Of course, if your language already provides a good shuffle library function, use that in preference to reinventing the wheel. If you're using Java, look at Collections.shuffle. In Python, look at random.shuffle. In Perl, List::Util::shuffle.)
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

May 2017

S M T W T F S
 123456
78910111213
14151617181920
212223242526 27
28293031   

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Sep. 19th, 2017 06:43 pm
Powered by Dreamwidth Studios