Merge pull request kennyledet#89 from lichtsprung/master

jcla1 · jcla1 · commit 31ec4cfb7d2c · 2013-12-31T08:31:40.000-08:00
added fisher-yates in scala
diff --git a/Fisher-Yates/Scala/lichtsprung/fisheryates_shuffle.scala b/Fisher-Yates/Scala/lichtsprung/fisheryates_shuffle.scala
@@ -0,0 +1,20 @@
+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
+  }
+}
diff --git a/Fisher-Yates/Scala/lichtsprung/fisheryates_shuffle_test.scala b/Fisher-Yates/Scala/lichtsprung/fisheryates_shuffle_test.scala
@@ -0,0 +1,21 @@
+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
+  }
+}
