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_06_Permutationen_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)
  }

  println(Perm(List("a", "b", "c", "d")).mkString("\n"))

}