How do you generate a shuffled sequence with ScalaCheck?

Question

I've been trying to generate shuffled sequences with scalacheck. Scalacheck doesn't provide any generator to do it straightforwardly, and I couldn't find any easy answer online. After a bit of thinking, below is how I did it. I hope others will find if useful.

Answer 1

org.scalacheck.Gen.pick(n: Int, l: Iterable[T]): Gen[Seq[T]] picks n distinct elements from l in random order. Call pick with n = l.length, and you will generate a randomly

Answer 2

def shuffle[T](s: Seq[T], prefix: Seq[T] = Vector()): Gen[Seq[T]] =
    if (s.length == 0) Gen.const(prefix.toSeq)
    else
      Gen.choose(0, s.length - 1)
        .flatMap { i => 
          shuffle(
            s.take(i) ++ s.takeRight(s.length - i - 1), 
            prefix :+ s(i)) }

Answer 3

You could use a collection shuffling algorithm (such as the one in scala.util.Random) to obtain a clearer solution:

/**
 * This represents a potential list shuffling. It
 * acts as a pure function - when applied to the
 * same list it always returns the same result
 */
class Shuffling(seed: Int) {
  def apply[T](xs: Seq[T]): Seq[T] = {
    val r = new scala.util.Random(seed)
    r.shuffle(xs)
  }
}

import org.scalacheck.Arbitrary._
import org.scalacheck.Gen

val shufflingGen: Gen[Shuffling] = arbitrary[Int].map(new Shuffling(_))

The above snippet defines a shuffling - a possible re-ordering of a list. It also defines a generator that provides arbitrary shuffling instances. The following example shows how you would use a shuffling to re-order a range of integers:

def shuffledRange(n: Int): Gen[Seq[Int]] = {
  for {
    shuffling <- shufflingGen
  } yield shuffling(Range(0, n))
}

It may seem odd to add one level of indirection in the form of the Shuffling class - we could just as well apply Random.shuffle directly on the list. This is because we want to avoid an additional source of randomness in addition to the implicit randomizing Scalacheck is already doing in the background - the source of randomness in the shuffling comes from a scalacheck generator.

One benefit to this would be the reproducibility of generated cases (whenever Scalacheck will support it).