Sunday, August 16, 2015

Fisher-Yates Shuffle in Scala

This post describes the Fisher-Yates algorithm to shuffle randomly a sequence of objects.


Overview
The generation of a sequence of randomly ordered elements from an existing sequence is a common problem. How can you be sure if the new sequence of items is actually randomly generated?
The Fisher-Yates shuffle algorithm (a.k.a. Donald Knuth shuffle) produces unbiased permutations with a similar likelihood.
One important benefit of Fisher-Yates is the ability to shuffle the elements of the sequence, in place.

Note:
There are several interpretations of the shuffling algorithm. This post describes the implementation of the most common Fisher-Yates algorithm

Fisher-Yates
Let's look at the implementation of Fisher-Yates
Here is the Fisher-Yates in a nutshell;
Let's consider an array arr of n elements
For each array index k from n-1 to 1
  Select a random value m  between k and 0
  Swap arr[r] and arr[k]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates[T](t: Seq[T]): Seq[T] = {

  setSeed(System.currentTimeMillis)
  
  (0 until t.size).foreach (n => {
     val randomIdx = n + nextInt(t.size-n)
     val tmp = t(randomIdx)
     t.update(randomIdx, t(n))
     t(n) = tmp
  })
  t
} 

The Fisher-Yates algorithm executes as an iteration with the following two steps:
  • Select a random item in the remaining sequence< (line 6)/li>
  • Swap the randomly selected item with the current item (lines 8,9)

Fast Fisher-Yates implementation
The performance of the Fisher-Yates algorithm can be improved by implementing the swapping of the randomly selected item with the current time in-place using bit manipulation operators.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def fisherYates2(seq: mutable.Seq[Int]): IndexedSeq[Int] = {
  require(seq.size > 0, "Undefined argument")

  setSeed(System.currentTimeMillis)
  (0 until seq.size).map(i => {
     var randomIdx: Int = i + nextInt(seq.size-i)
     seq(randomIdx) ^= seq(i)
     seq(i) = seq(randomIdx) ^ seq(i) 
     seq(randomIdx) ^= (seq(i))
     seq(i)
  })
}

The following code snippet tests the two implementations of the Fisher-Yates shuffling algorithm.
  val input = Array[Char](
    'a', 't', '4', '&', '9', '2', 'z', 'y', 'r', '8', '*', '?'
  )
  println(fisherYates[Char](input).mkString(","))
  // t,&,*,2,a,r,4,z,?,y,8,9

  println(fisherYates2(Array.tabulate(34)(n => n)).mkString(","))
  // 9,24,11,29,1,31,28,20,6,18,23,0,13,17,22,0,27,
  // 4,16,7,25,14,30,32,5,12,8,19,21,0,0,33,26,0
Note:
Scala standard library provides developers with a shuffling method: Random.shuffle.

Reference

1 comment:

  1. Seq is not mutable.

    def fisherYates[T](t: Buffer[T]): Buffer[T] = {

    r.setSeed(System.currentTimeMillis)

    (0 until t.size).foreach (n => {
    println(n)
    val randomIdx = n + r.nextInt(t.size-n)
    val tmp = t(randomIdx)
    t.update(randomIdx, t(n))
    t(n) = tmp
    })
    t
    }

    ReplyDelete