Skip to main content

News

Topic: [code] Simple array randomizer (aka shuffle) (Read 2425 times) previous topic - next topic

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
[code] Simple array randomizer (aka shuffle)
Array randomizer, both non-destructive (by copy) and destructive (in-place). It's quite possibly the shortest way to write a shuffle and I can't believe I didn't realize it until now.

Code: (javascript) [Select]

/** non-destructive randomizer **/
function shuffle(arr) {
var r = arr.slice();
return r.sort(function(a,b){
return Math.random()-Math.random();
});
}

Code: (javascript) [Select]

/** destructive randomizer **/
function shuffle(a,b){return Math.random()-Math.random();}
// ... then sort in place ...
someArray.sort(shuffle);


The two Math.random calls are really the only thing stopping it from being as fast as a normal sort function. Array.sort is inherently destructive and I wanted to operate on a copy; you can use the in-place shuffle if you don't need the copy. You can also modify the sort function to use properties of a and b like any other sort function.
  • Last Edit: August 30, 2013, 03:20:43 pm by N E O

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Simple array randomizer (aka shuffle)
Reply #1
Nicely done! There is shorter, :P

Code: (javascript) [Select]

[1, 2, 3, 4, 5].sort(function() { return 0.5 - Math.random();});


Edit:
Probably a little faster too now that I think about it.
  • Last Edit: August 30, 2013, 12:18:25 am by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • miniSphere Developer
Re: [code] Simple array randomizer (aka shuffle)
Reply #2
@NEO:
Your "non-destructive" version is still destructive.  var r = arr just aliases the original array.  You have to use slice to get a copy:

Code: (javascript) [Select]
var r = arr.slice();
miniSphere 5.0.1 - Cell compiler - SSj debugger - thread | on GitHub
For the sake of our continued health I very much hope that Fat Cerberus does not become skilled enough at whatever arcane art it would require to cause computers to spawn enourmous man eating pigs ~Rhuan

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
Re: [code] Simple array randomizer (aka shuffle)
Reply #3
@Lord English - aaugh, really? Not a copied value? That's annoying. Code updated to use slice, thanks!

@Radnen - Yours is indeed shorter and for unweighted sorting definitely faster; mine originally started as the somewhat weighted a*Math.random()-b*Math.random(), then I decided to remove the weights because they're both still random. It made more sense my way when it was "weighted" and I'll probably edit it to restore the weights.

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • miniSphere Developer
Re: [code] Simple array randomizer (aka shuffle)
Reply #4
Yeah, an array is just an object in JS so unless you explicitly make a copy of it you're just passing a reference around.
miniSphere 5.0.1 - Cell compiler - SSj debugger - thread | on GitHub
For the sake of our continued health I very much hope that Fat Cerberus does not become skilled enough at whatever arcane art it would require to cause computers to spawn enourmous man eating pigs ~Rhuan

  • N E O
  • [*][*][*][*][*]
  • Administrator
  • Senior Administrator
Re: [code] Simple array randomizer (aka shuffle)
Reply #5
Super bump.

How naive I was about shuffle previously! Use the Fisher-Yates shuffle from now on (it's also faster than my original, O(n) acc. to author):

Code: (javascript) [Select]

function shuffle(arr) {
var n = arr.length, t, i;
while (n) {
i = Math.random() * n-- | 0; // 0 ≤ i < n
t = arr[n];
arr[n] = arr[i];
arr[i] = t;
}
return arr;
}


Just read this post on visualizing algorithms and it made me think of this thread, particularly the section on shuffling bias.

  • Radnen
  • [*][*][*][*][*]
  • Senior Staff
  • Wise Warrior
Re: [code] Simple array randomizer (aka shuffle)
Reply #6
Yes, it has since been built into Link, thanks to Lord English. :)

Code: (javascript) [Select]

var shuffled = Link([0, 1, 2, 3, 4]).shuffle();
  • Last Edit: July 03, 2014, 08:05:49 pm by Radnen
If you use code to help you code you can use less code to code. Also, I have approximate knowledge of many things.

Sphere-sfml here
Sphere Studio editor here

  • Fat Cerberus
  • [*][*][*][*][*]
  • Global Moderator
  • miniSphere Developer
Re: [code] Simple array randomizer (aka shuffle)
Reply #7
Yeah, Fisher-Yates is the best way to shuffle.  It's ridiculously simple to implement and is literally the single most efficient way to do it--and given a good RNG, all permutations are possible and equally likely to occur.

As it turns out, sort() should never be used to shuffle, since sorting algorithms are designed around the assumption that the comparison function is consistent (one that isn't, as noted in the article NEO posted, is by definition broken).  Depending on the sorting algorithm used, this can even cause an infinite loop!
miniSphere 5.0.1 - Cell compiler - SSj debugger - thread | on GitHub
For the sake of our continued health I very much hope that Fat Cerberus does not become skilled enough at whatever arcane art it would require to cause computers to spawn enourmous man eating pigs ~Rhuan