StrangeUrn.scala

import scala.collection.immutable.{IndexedSeq => Vec}
import scala.annotation.tailrec
import scala.util.Random

def coin()(implicit random: Random): Boolean = random.nextBoolean()

object StrangeUrn {
  def apply[A](set: Set[A])(implicit random: Random): StrangeUrn[A] = {
    require(set.nonEmpty)
    new Impl(in = random.shuffle(set.toIndexedSeq), out = Vector.empty)
  }

  private final class Impl[A](in: Vec[A], out: Vec[A]) extends StrangeUrn[A] {
    def choose()(implicit random: Random): (A, StrangeUrn[A]) = in match {
      case head +: tail => (head, new Impl(tail, out :+ head))
      case _ =>
        @tailrec
        def loop(outRem: Vec[A], inAcc: Vec[A]): Vec[A] = outRem match {
          case a +: b +: tail =>
            val (chosen, outRem1) = if (coin()) (a, b +: tail) else (b, a +: tail)
            loop(outRem1, inAcc :+ chosen)

          case head +: tail => loop(tail, inAcc :+ head)
          case _ => inAcc
        }

        val newIn  = loop(out, Vector.empty)
        val newUrn = new Impl(newIn, Vector.empty)
        newUrn.choose()
    }
  }
}
trait StrangeUrn[+A] {
  def choose()(implicit random: Random): (A, StrangeUrn[A])
}

val set = Set(1 to 10: _*)
implicit val random = new Random

val (xs, _) = ((Vector.empty[Int], StrangeUrn(set)) /: (1 to 100)) { 
  case ((res, urn), _) => 
    val (chosen, urn1) = urn.choose()
    (res :+ chosen, urn1)
}

xs.grouped(10).foreach(println)

/* Example:

Vector(4, 5, 7, 1, 2, 3, 9, 10, 8, 6)
Vector(4, 7, 5, 2, 3, 9, 10, 1, 6, 8)
Vector(4, 7, 5, 3, 2, 9, 10, 6, 1, 8)
Vector(7, 5, 4, 2, 9, 3, 6, 1, 8, 10)
Vector(7, 4, 2, 9, 5, 6, 1, 3, 10, 8)
Vector(4, 7, 9, 2, 6, 5, 1, 10, 3, 8)
Vector(4, 9, 7, 6, 2, 1, 10, 3, 8, 5)
Vector(4, 9, 6, 7, 1, 10, 2, 3, 5, 8)
Vector(4, 9, 7, 6, 1, 2, 3, 5, 10, 8)
Vector(9, 4, 6, 1, 7, 3, 2, 10, 8, 5)
*/