ShuffleBag Ports

Fri, 2008-09-12 07:45 — jh

: The art of shuffling

What it says on the tin, really

Here you'll get Flash (AS3), haXe, JavaScript, PHP, Perl, and Python ports of my continuous shuffled sequence algorithm. (Update: There are C# and C++ versions in the comments.) As usual the code is available under a Zero-clause BSD-style license, which means you can use it in any way you like.

All implementations utilize an un-seeded default source of randomness. If determinism is required, you'll only need to hand over a PRNG and use that one instead. Or hand the seed over and initialize the PRNG with that one as the original Java version did it.

If you port it to other languages or if you modify it a bit (e.g. as outlined above), you'll have to verify that it works correctly. Fortunately testing it isn't that hard. E.g. if you add "X" and "O" and call next four times you should receive one of the following sequences:

XXOO
OOXX
XOOX
OXXO
XOXO
OXOX

If you get a sequence which wasn't listed above or not all of those permutations (in a loop — obviously) something went wrong somewhere. Typically it will be an off-by-one error in the grab line or the cursor is off by one. Read the code carefully and you should be able to locate the issue quickly. Either that or take a semi-random guess and see if it passes the test. ;)

haXe — ShuffleBag.hx

import Math;
class ShuffleBag{
    var data:Array<Int>;
    var cursor:Int;
    public function new(){
        data=[];
        cursor=-1;
    }
    public function add(item:Int,quantity:Int=1){
        for(i in 0...quantity)
            data.push(item);
        cursor=data.length-1;
    }
    public function next(){
        if(cursor<1){
            cursor=data.length-1;
            return data[0];
        }
        var grab:Int=Std.random(cursor+1);
        var temp:Int=data[grab];
        data[grab]=data[cursor];
        data[cursor]=temp;
        cursor--;
        return temp;
    }
}

Example usage:

var sb:ShuffleBag=new ShuffleBag();
sb.add(1); //add 1
sb.add(2,3); //add 2 3 times
var i:Int=sb.next(); //1 - 25%, 2 - 75%

AS3 — ShuffleBag.as

package{
    public class ShuffleBag{
        private var data:Array=[];
        private var cursor:int;
        public function ShuffleBag(){
            cursor = -1;
        }
        public function size():int {
            return data.length;
        }
        public function add(item:int,quantity:int=1):void{
            for (var i:int = 0; i < quantity;i++){
                data.push(item);
            }
            cursor=data.length-1;
        }
        public function next():int{
            if(cursor<1){
                cursor=data.length-1;
                return data[0];
            }
            var grab:int=Math.floor(Math.random()*(cursor+1));
            var temp:int=data[grab];
            data[grab]=data[cursor];
            data[cursor]=temp;
            cursor--;
            return temp;
        }
    }
}

Example usage:

var sb:ShuffleBag=new ShuffleBag();
sb.add(1); //add 1
sb.add(2,3); //add 2 3 times
var i:int=sb.next(); //1 - 25%, 2 - 75%

JavaScript — shufflebag.js

function ShuffleBag(){
  this.data=[];
  this.cursor=-1;

  function add(thingy){
    if(arguments.length>1){
      for(var i=arguments[1];i>0;--i)
        this.data.push(thingy);
    }else{
      this.data.push(thingy);
    }
    this.cursor=this.data.length-1;
  }

  function next(){
    if(this.cursor<1){
      this.cursor=this.data.length-1;
      return this.data[0];
    }
    var grab=Math.floor(Math.random()*(this.cursor+1));
    var temp=this.data[grab];
    this.data[grab]=this.data[this.cursor];
    this.data[this.cursor]=temp;
    this.cursor--;
    return temp;
  }

  this.add=add;
  this.next=next;
}

Example usage:

var sb=new ShuffleBag();
sb.add(1); //add 1
sb.add(2,3); //add 2 3 times
var i=sb.next(); //1 - 25%, 2 - 75%

PHP — ShuffleBag.php

<?php
class ShuffleBag{
  private $data=array();
  private $cursor=-1;
  private $size=0;
  public function add($item,$quantity=1){
    for($i=0;$i<$quantity;$i++){
      $this->data[]=$item;
      $this->size++;
    }
    $this->cursor=$this->size-1;
  }
  public function next(){
    if($this->cursor<1){
      $this->cursor=$this->size-1;
      return $this->data[0];
    }
    $grab=rand(0,$this->cursor);
    $temp=$this->data[$grab];
    $this->data[$grab]=$this->data[$this->cursor];
    $this->data[$this->cursor]=$temp;
    $this->cursor--;
    return $temp;
  }
}
?>

Example usage:

$sb=new ShuffleBag();
$sb->add(1); //add 1
$sb->add(2,3); //add 2 3 times
$i=sb->next(); //1 - 25%, 2 - 75%

Perl — ShuffleBag.pm

#!/usr/bin/perl
package ShuffleBag;
use strict;

my @data;
my $cursor=-1;

sub new{
    my($type)=$_[0];
    my($self)={};
    bless($self,$type);
    return($self);
}

sub add{
    my($foo,$value,$quantity)=@_;
    if(defined($quantity)){
        for(my $i=0;$i<$quantity;$i++){
            push(@data,$value);
        }    
    }else{
        push(@data,$value);
    }
    $cursor=scalar(@data)-1;
}


sub next{
    if($cursor<1){
        $cursor=scalar(@data)-1;
        return $data[0];
    }
    my $grab=int(rand($cursor+1));
    my $temp=$data[$grab];
    $data[$grab]=$data[$cursor];
    $data[$cursor]=$temp;
    $cursor--;
    return $temp;
}

Example usage:

my $sb=ShuffleBag;
$sb->add(1); #add 1
$sb->add(2); #add 2 3 times
my $i=sb->next; #1 - 25%, 2 - 75%

Python — shufflebag.py

#!/usr/bin/env python

import random

class ShuffleBag:
    def __init__(self,seed=None):
        self.data=[]
        self.cursor=-1
        random.seed(seed)

    '''add items'''
    def add(self, val, quantity=1):
        for i in range(quantity):
           self.data.append(val)
        self.cursor=len(self.data)-1

    '''return one item'''
    def next(self):
        if self.cursor<1:
            self.cursor=len(self.data)-1
            return self.data[0]
        grab=random.randint(0,self.cursor)
        temp=self.data[grab]
        self.data[grab]=self.data[self.cursor]
        self.data[self.cursor]=temp
        self.cursor=self.cursor-1
        return temp

Example usage:

sb=shufflebag.ShuffleBag()
sb.add(1) #add 1
sb.add(2,3) #add 2 3 times
i=sb.next(); #1 - 25%, 2 - 75%

jh's blog

Comments

Wed, 2008-12-17 23:45 — Anonymous

More Pythonic version

Hi, great post and a nice algorithm. I am writing a puzzle game that will use this algorithm for the pieces, and thought I might offer my Python implementation (feel free to use it any way you like):

http://pastebin.com/f707de4c5

As you can see, using generators instead of a class here simplifies the code a lot.

[Pasted the code here for you. — jh]

import random



def ShuffleBag(items, seed=None):
    """Create a new shuffled bag using the elements in items.

    Items can be a dict of (item : frequency) pairs, or an iterable.
    """
    try:
        items = sum(([item] * freq for (item, freq) in items.items()), [])
    except AttributeError:
        items = list(items)
    random.seed(seed)
    while True:
        n = len(items)
        for i in range(n):
            grab = random.randint(i, n-1)
            items[i], items[grab] = items[grab], items[i]
            yield items[i]
        


sb = ShuffleBag([1, 2, 2, 2])
print sb.next() # 1 - 25%, 2 - 75%

sb = ShuffleBag({1:1, 2:3})
print sb.next() #1 - 25%, 2 - 75%

Thu, 2008-12-18 00:26 — jh

re: More Pythonic version

Heh. That looks pretty weird. Cool stuff though. :)

Well, as you can probably tell my version is a rather straight port. All versions are basically the very same thing. The only version which is fundamentally different is the Java one. It's a tad more low level since it manages the growth of the underlying array itself (which should make it easy to port it to say... C++).

Thu, 2008-12-18 03:32 — Anonymous

re: More Pythonic version

Yeah, it does look weird because it's something not found in a lot of OO languages, which typically just treat functions as being owned by classes instead of being objects in their own right. One of the things I love about Python is it lets you choose between procedural, OO, and functional styles, whichever is more appropriate for each situation. Although I still think the PLT-Scheme version looks weirder ^_^

Fri, 2009-06-26 08:03 — Anonymous

C# Port

I did an (almost) straight port of GShuffleBag to C#. Like the versions above, there's no documentation (yet, I'll get there). It's LGPL'd with the rest of the library, but that's still a liberal licence to let you do what you want with it, and you can feel free to download the single file and use it in your program

You can download it at: http://liboxide.svn.sourceforge.net/viewvc/liboxide/trunk/Oxide/Collecti...

Wed, 2009-07-15 23:40 — Anonymous

C++ version, for fun

template<typename T>
class ShuffleBag {
    public:
        ShuffleBag() : cursor_(-1) {}

        void add(const T& value) {
            data_.push_back(value);
            cursor_ = data_.size() - 1;
        }

        void add(const T& value, int count) {
            while (count-- > 0)
                add(value);
        }

        T next() {
            if (cursor_ < 1) {
                cursor_ = data_.size() - 1;
                return data_[0];
            }

            const int grab = random() % (cursor_ + 1);
            const T temp = data_[grab];
            swap(data_[grab], data_[cursor_]);
            cursor_--;
            return temp;
        }
    private:
        vector<T> data_;
        int cursor_;
};

kaioa.com