Assign relations between people with specified constraints. "Secret Pal" or "Amigo Invisible" style :)

SecretPal.scala

import scala.util.Random

/** Azareus: assign relations between people with single way constraints. */
trait Azareus {
  val r = new Random()
  type Person = String
  type Couple = (Person, Person)
  type Constraint = (Person, Person)
  type Result = List[Couple]

  /** Return random result of couples given set of people and constraints. */
  def azareus(people: List[Person], rules: List[Constraint]) : Result =
    results(r.shuffle(people)).find(result => result.forall(!rules.contains(_)))
    .getOrElse(throw new IllegalArgumentException("Impossible!"))

  /** Return all possible combinations results (lazy approach!). */
  def results(people: List[Person]) = people.permutations.map(p => relations(p :+ p.head))

  /** Circular list of people to couple results. */
  def relations(people: List[Person]) : Result = people match {
    case x :: Nil => Nil
    case x :: xs => (x, xs.head) :: relations(xs)
  }
}

object AzareusMain extends App with Azareus {
  val people = List("Peter","Luke","Vic","Claire","Joe")
  val constraints = List(("Peter", "Claire"), ("Claire","Peter"), ("Vic","Luke"), ("Luke", "Vic"))
  println(azareus(people, constraints))
}