fisher-yates


See On Github

Data

Tags

shuffle

Source Code

import scala.util.Random

object fisheryates_shuffle {

  def shuffle_inplace[T](values: Array[T]): Unit = {
    for (i ← values.size to 1) swap(i, Random.nextInt(i), values)
  }

  def shuffle[T](values: Array[T]): Array[T] = {
    val shuffled = values.clone()
    for (i ← shuffled.size to 1) swap(i, Random.nextInt(i), shuffled)
    shuffled
  }

  private def swap[T](x: Int, y: Int, s: Array[T]): Unit = {
    val tmp = s(x)
    s(x) = s(y)
    s(y) = tmp
  }
}
import org.scalatest.{ Matchers, FlatSpec }
import fisheryates_shuffle._

class fisheryates_shuffle_test extends FlatSpec with Matchers {

  "Fisher-Yates Shuffle (inplace)" should "shuffles the values of the array inplace" in {
    val values = Array(1, 2, 3, 4, 5)
    shuffle_inplace(values)
    values should contain allOf (1, 2, 3, 4, 5)
    values should contain inOrder (1, 2, 3, 4, 5)
    values.permutations.find(_.deep == values.deep).nonEmpty shouldBe true
  }

  "Fisher-Yates Shuffle" should "return a random permutation of the source array" in {
    val values = Array(1, 2, 3, 4, 5)
    val shuffled = shuffle(values)
    shuffled should contain allOf (1, 2, 3, 4, 5)
    values should contain inOrder (1, 2, 3, 4, 5)
    values.permutations.find(_.deep == shuffled.deep).nonEmpty shouldBe true
  }
}