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

3 comments:

  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
  2. When finding that correct rhythm, that specific example that drive the fish totally nuts for your bait, you generally need to remember: Slow-Fast-Medium. These are the three velocities you need to alter with so as to get to that rhythm.fishing holiday in thailand

    ReplyDelete

  3. اعالى الخليج تقدم افضل خدمات نقل العفش الدولى المتميزه باسعار متميزة ومنها :

    شركة شحن عفش من الرياض الى دبي
    نقل عفش من الرياض الى الاردن شحن عفش من الرياض الى الاردن

    ReplyDelete