package kapitel_04

/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 4, Listen: Immer einer nach dem anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

object AuD_04_07_PermSort_App extends App {

  def Perm[T](l: List[T]): List[List[T]] = l match {
    case Nil =>
      Nil :: Nil
    case x :: rest =>
      Ins(x, Perm(rest))
  }

  def Ins[T](x: T, L: List[List[T]]): List[List[T]] =
    L.flatMap(l => InsH(x, l))

  def InsH[T](x: T, l: List[T]): List[List[T]] = l match {
    case Nil =>
      (x :: Nil) :: Nil
    case h :: t =>
      (x :: l) :: InsH(x, t).map(l1 => h :: l1)
  }

  def isSorted(l: List[Int]): Boolean = {

    !l.dropRight(1).zip(l.tail).exists {
      case (x, y) =>
        x > y
    }
  }

  def PermSort(l: List[Int]): List[Int] = {
    for (p <- Perm(l)) {
      if (isSorted(p))
        return p
    }
    throw new IllegalArgumentException("List can not be sorted")
  }

  val lst = List(-1,5,3,6,7,-7)

  var i = 0
  for (p <- Perm(lst)) {
    i = i+1
    if (p == List(-7,-1,3,5,6,7)) println(s"HEUREKA => isSorted($p) = ${isSorted(p)}")
  }

  PermSort(lst)

}