package kapitel_13 /** * Beispiel aus * * - Algorithmen und Datenstrukturen für Dummies * - von Andreas Gogol-Döring und Thomas Letschert * - Verlag Wiley-VCH; Oktober 2019 * - Kapitel 13, Dynamisches Programmieren * * @author A. Gogol-Döring, Th. Letschert */ import scala.collection.mutable.ListBuffer object AuD_13_14_GetAlgnment_App extends App { def getAlignment(a: String, b: String): List[(Char, Char)] = { val n = a.length val m = b.length val Tab = Array.ofDim[Int](n+1, m+1) for(i <- 0 to n; j <- 0 to m) { Tab(i)(j) = (i, j) match { case (0, _) => j case (_, 0) => i case (_, _) => List( Tab(i - 1)(j - 1) + (if (a(i-1) != b(j-1)) 1 else 0), Tab(i - 1)(j) + 1, Tab(i)(j - 1) + 1 ).min } } var i = n var j = m val A: ListBuffer[(Char, Char)] = ListBuffer() while (i > 0 || j > 0) { if (i == 0) { A.prepend(('~', b(j-1))) j = j-1 } else if (j == 0) { A.prepend((a(j-1), '~')) i = i - 1 } else { val D = Tab(i-1)(j-1) + (if (a(i-1) != b(j-1)) 1 else 0 ) val V = Tab(i-1)(j) val H = Tab(i)(j-1) if (D == Tab(i)(j)) { A .prepend((a(i-1), b(j-1))) i = i - 1 j = j - 1 } else if (V == Tab(i)(j)) { A.prepend((a(i-1), '~')) i = i - 1 } else if (H == Tab(i)(j)) { A.prepend(('~', b(j-1))) j = j -1 } } } A.toList } // NeedlemanWunsch // Rückverweise rekonstruieren (speichereffizienter) val a1 = getAlignment("LIEBEN", "FLIEGEN") println(a1.map( _._1).mkString(" ")) // ~ L I E B E N println(a1.map( _._2).mkString(" ")) // F L I E G E N def alignIiter(x: String, y: String): List[(Char, Char)] = { val align = Array.ofDim[List[(Char, Char)]](x.length+1, y.length+1) for (n <- 0 to x.length; m <- 0 to y.length) { (n, m) match { case (_, 0) => align(n)(m) = (0 until n).map(i => (x(i), '~')).toList case (0, _) => align(n)(m) = (0 until m).map(j => ('~', y(j))).toList case (i, j) => align(n)(m) = List( (x(i - 1), y(j - 1)) :: align(i - 1)(j - 1), (x(i - 1), '~') :: align(i - 1)(j), ('~', y(j - 1)) :: align(i)(j - 1) ).minBy( _.count { case (c1, c2) => c1 != c2 } ) } } align(x.length)(y.length).reverse } println() // Rueckverweise als Bestandteil der Tabelle (einfacher) val a2 = alignIiter("LIEBEN", "FLIEGEN") println(a1.map( _._1).mkString(" ")) // ~ L I E B E N println(a1.map( _._2).mkString(" ")) // F L I E G E N }