AS3 Vector shuffle / randomize

Posted by Philip Bulley | Filed under Actionscript 3

UPDATE: Please see comments below for a shuffle technique using the efficient Fisher-Yates algorithm.

Whilst working on an AS3 project, I figured I needed to shuffle the order of a Vector. A quick Google search looking for a code snippet that will shuffle the order of an Array will produce many results (although I’d most likely use the nicely packaged CasaLib’s ArrayUtil.randomize()). But the same is not true (at least as of writing) for shuffling the order of a Vector.

So this post is for anyone stumbling on in from Google, requiring a quick “I can’t be bothered to think about it” solution:

1
2
3
4
5
6
7
8
9
10
11
function shuffleVector( a:Object, b:Object ):int
{
        return Math.floor( Math.random() * 3 - 1 );
}

// Some quick timeline code to test it
var v:Vector.<String> = new Vector.<String>();
v.push('one', 'two', 'three', 'four');
trace( v );    // Original
v.sort( shuffleVector );
trace( v );    // Shuffled

Just to note, Array.sort() has never won any awards for code execution speed, so it’s likely that Vector.sort() won’t either.

Tags:

Permalink | July 20th, 2010

3 Responses to “AS3 Vector shuffle / randomize”

  1. Ian Calvert
    September 1st, 2010 at 11:22 am

    I’m not sure that’ll work. The sort function should take two objects and return a number which is negative if a <b> b. Try 0.5 – Math.random() instead.

    It’s also worth noting that this is not a perfect shuffle. A Fischer-Yates (Knuth) would be faster and correct. Link: http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

    Untested implementation:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    function swap(vect : Vector, a : uint, b : uint) : void{
        var temp : Object = vect[a];
        vect[a] = vect[b];
        vect[b] = temp;
    }

    function sort(vect : Vector) : void{
      var totalItems : uint = vect.length;
      for (var i : uint = 0; i &lt; totalItems; i++){
        swap(vect, i, i + uint(Math.random()*(totalItems - i));
      }
    }
  2. Ian Calvert
    September 1st, 2010 at 11:23 am

    Urg, formatting killed the first paragraph.

    The sort function should return a negative number if a is less than b, zero if they are equal and a positive number if a is greater than b.

  3. Philip Bulley
    September 1st, 2010 at 1:02 pm

    Hi Ian,

    The random functionality definitely works fine. Yours also works and is surely faster seeing as you’re not using Math.floor(). I figured I’d need to return an integer, but returning a float seems to be cast successfully to int.

    Regardless of that, thanks for posting about the Fisher Yates algorithm… I’ve tested and slightly amended your example:

    Tested implementation using Fisher Yates:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    function swap( vect:Object, a:uint, b:uint ):void
    {
        var temp:Object = vect[a];
        vect[a] = vect[b];
        vect[b] = temp;
    }
    function sort( vect:Object ):void
    {
        var totalItems : uint = vect.length;
        for (var i : uint = 0; i < totalItems; i++)
            swap( vect, i, i + uint( Math.random() * (totalItems - i) ) );
    }

    var v:Vector.<String> = new Vector.<String>();
    v.push('one', 'two', 'three', 'four');
    trace( v );    // Original
    sort( v );
    trace( v );    // Shuffled

    I changed the sort method’s signature to vect:Object, because vect:Vector understandably doesn’t work. But neither does vect:Vector.<*> or vect:Vector.<Object>. Not sure why the compiler doesn’t like the last two???

    Thanks for sharing Ian!

Leave a Reply