object YoungTableaux {

  type Tableau = Seq[Seq[Int]]

  def empty: Tableau = Seq.empty

  def youngTableaux(n: Int): Seq[Tableau] = {
    val maxK = n*n - 1

    def t(tableau: Tableau, k: Int): Seq[Tableau] = {
      if (k > maxK) Seq(tableau)
      else {
        val top: Option[Tableau] =
          tableau
            .headOption
            .filter(_.size < n)
            .map(r => tableau.updated(0, r :+ k))

        val bottom: Option[Seq[Seq[Int]]] =
          if (tableau.size >= n) None
          else Some(tableau :+ Seq(k))

        val mid: Seq[Seq[Seq[Int]]] =
          for {
            i <- 1 until tableau.size
            if tableau(i).size < tableau(i - 1).size
          } yield tableau.updated(i, tableau(i) :+ k)

        top.toSeq ++ mid ++ bottom.toSeq
      }
    }

    (0 to maxK).foldLeft(Stream(empty)) {
      case (tableaux, k) => tableaux.flatMap(t(_, k))
    }
  }

  def stringify(tableau: Tableau): String =
    tableau.map(r => r.map("%3d".format(_)).mkString).mkString("\n")
}