implicit class RichInt(n: Int) { def ! : Int = (1 to n).product }
def sum(x: Int) = x * (x + 1) / 2

def combination[T](set: Set[T], size: Int): Set[Set[T]] = {
  def solve[T](list: List[T], size: Int): Set[Set[T]] = {
    if(list.size < size) {
      Set.empty[Set[T]]
    } else {
      if(size == 0) {
        Set(Set.empty[T])
      } else if(size == 1) {
        list.map(item => Set(item)).toSet
      } else {
        def loop(remain: List[T], set: Set[Set[T]] = Set.empty[Set[T]]): Set[Set[T]] = {
          remain match {
            case Nil => set
            case item :: remain if remain.size < size - 1 => set
            case item :: remain =>
              loop(remain, set ++ solve(remain, size - 1).map(set => set + item))
          }
        }
        loop(list)
      }
    }
  }
  solve(set.toList, size)
}

def coefficient(n: Int, order: Int): Int = {
  val numbers = (1 to n).toSet
  combination(numbers, n - order).toList.map(set => set.product).sum
}

def toFormula(cs: List[Int]): String = cs.zipWithIndex.reverse.map {
  case (c, 0) => s"$c"
  case (1, o) => s"x ^ $o"
  case (c, o) => s"$c * x^$o"
}.mkString(" + ")

def toFormula(cs: List[Double]): String = cs.zipWithIndex.reverse.map {
  case (c, 0.0) => s"$c"
  case (1.0, o) => s"x ^ $o"
  case (c, o) => s"$c * x^$o"
}.mkString(" + ")

def coefficients(n: Int): (List[Int], Int) = {
  val product = n !

  val cs = (product :: (1 to n).toList.map {
    o => coefficient(n, o)
  })

  (cs.toList, product)
}

(1 to 10).map { n =>
  val cs = coefficients(n) match {
    case (cs, p) => cs.map{ c => c.doubleValue / p }
  }
  toFormula(cs)
} .foreach(println)