package kapitel_14

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 14, Näherungslösungen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_14_05_SetCovering_App extends App {

  case class AllSubLists[A](lst: List[A]) extends Iterable[List[A]] {
    override def iterator: Iterator[List[A]] =
      allSubLists(lst).iterator

    private def allSubLists(lst: List[A]): List[List[A]] = lst match {
      case Nil =>
        List(Nil)
      case head :: tail =>
        for (s <- allSubLists(tail);
             b <- List(List(head), Nil)
             ) yield s ++ b
    }
  }

  /*
   * Mit AllSubLists (siehe Kapitel 8)
   */

  /**
   * @param S Liste von Teilmengen von R
   * @param R eine Menge
   * @tparam A Typ der mengenelemente
   * @return kleinste Teilliste von S die r abdeckt
   */
  def SetCovering[A](S: Set[Set[A]], // Liste von Teilmengen von R
                     R: Set[A]
                    ): List[Set[A]] = {
    var result: List[Set[A]] = Nil
    var count = Int.MaxValue
    for (t <- AllSubLists(S.toList)) {
      val join = t.foldLeft(Set[A]())( (acc, s) => acc ++ s)
      if (join == R && t.size < count) {
        count = t.size
        result = t
      }
    }
    result
  }

  /*
   * Etwas effizienter ist:
   */

  def SetCoveringG[A](S: Set[Set[A]], // Liste von Teilmengen von R
                   R: Set[A]
                  ): List[Set[A]] = {
    var result: List[Set[A]] = Nil
    var notCovered = R
    var sRemaining = S
    while (notCovered.nonEmpty) {
      val u: Set[(Set[A], Int)] = for (s <- sRemaining if s.nonEmpty)
        yield (s, notCovered.intersect(s).size)
      val s: Set[A] = u.maxBy(_._2)._1
      notCovered = notCovered.diff(s)
      sRemaining = sRemaining.diff(Set(s))
      result = s :: result
    }
    result
  }


  val R : Set[Int] = Set(0,1,2,3,4,5,6,7,8,9)
  val S: Set[Set[Int]] = Set (
      Set(0,1,2,3,4,7,8),
      Set(6,7),
      Set(9),
      Set(5),
      Set(3,4,5,6)
  )

  var scbf = SetCovering(S, R)
  println(scbf)

  var scgreed = SetCoveringG(S, R)
  println(scgreed)

}