String replacement

replace.sc

def concat(heads: List[Char], tails: List[String]): List[String] = {
  for {
    h <- heads
    t <- tails
  } yield h.toString + t
}

def replace(str: String, replacement_rules: Map[Char, List[Char]], max_replacements: Int): List[String] = {
  def replaceStep(str: String, replacements_count: Int): List[String] = {
    if (replacements_count == 0) List(str)
    else if (str.length == 0) List()
    else {
      val head = str.charAt(0)
      val tail = str.substring(1)
      val substitutions = replacement_rules.getOrElse(head, List())
      concat(List(head), replaceStep(tail, replacements_count)) :::
        concat(substitutions, replaceStep(tail, replacements_count - 1))
    }
  }
  (0 to max_replacements).flatMap(replacements => replaceStep(str, replacements)).toList
}

val replacement_rules = Map('i' -> List('x','y'), 'e' -> List('3', '5'))
print(replace("casine", replacement_rules, 2))