Scala/functional/without libs - check if string permutation of other

Question

How could you check to see if one string is a permutation of another using scala/functional programming with out complex pre-built functions like sorted()?

I'm a Python dev and what I think trips me up the most is that you can't just iterate through a dictionary of character counts comparing to another dictionary of character counts, then just exit when there isn't a match, you can't just call break.

Answer 1

Assume this is the starting point, based on your description:

val a = "aaacddba"
val b = "aabaacdd"
def counts(s: String) = s.groupBy(identity).mapValues(_.size)
val aCounts = counts(a)
val bCounts = counts(b)

This is the simplest way:

aCounts == bCounts  // true

This is precisely what you described:

def isPerm(aCounts: Map[Char,Int], bCounts: Map[Char,Int]): Boolean = {
  if (aCounts.size != bCounts.size)
    return false
  for ((k,v) <- aCounts) {
    if (bCounts.getOrElse(k, 0) != v)
      return false
  }
  return true
}

This is your method, but more scala-ish. (It also breaks as soon as a mismatch is found, because of how foreach is implemented):

(aCounts.size == bCounts.size) && 
    aCounts.forall { case (k,v) => bCounts.getOrElse(k, 0) == v }

(Also, Scala does have break.)

Also, also: you should read the answer to this question.

Answer 2

Another option using recursive function, which will also 'break' immediately once mismatch is detected:

import scala.annotation.tailrec

@tailrec
def isPerm1(a: String, b: String): Boolean = {
  if (a.length == b.length) {
    a.headOption match {
      case Some(c) =>
        val i = b.indexOf(c)
        if (i >= 0) {
          isPerm1(a.tail, b.substring(0, i) + b.substring(i + 1))
        } else {
          false
        }
      case None => true
    }
  } else {
    false
  }
}

Out of my own curiosity I also create two more versions which use char counts map for matching:

def isPerm2(a: String, b: String): Boolean = {
  val cntsA = a.groupBy(identity).mapValues(_.size)
  val cntsB = b.groupBy(identity).mapValues(_.size)
  cntsA == cntsB
}

and

def isPerm3(a: String, b: String): Boolean = {
  val cntsA = a.groupBy(identity).mapValues(_.size)
  val cntsB = b.groupBy(identity).mapValues(_.size)
  (cntsA == cntsB) && cntsA.forall { case (k, v) => cntsB.getOrElse(k, 0) == v }
}

and roughly compare their performance by:

def time[R](block: => R): R = {
  val t0 = System.nanoTime()
  val result = block    // call-by-name
  val t1 = System.nanoTime()
  println("Elapsed time: " + (t1 - t0) + "ns")
  result
}

// Match
time((1 to 10000).foreach(_ => isPerm1("apple"*100,"elppa"*100)))
time((1 to 10000).foreach(_ => isPerm2("apple"*100,"elppa"*100)))
time((1 to 10000).foreach(_ => isPerm3("apple"*100,"elppa"*100)))

// Mismatch
time((1 to 10000).foreach(_ => isPerm1("xpple"*100,"elppa"*100)))
time((1 to 10000).foreach(_ => isPerm2("xpple"*100,"elppa"*100)))
time((1 to 10000).foreach(_ => isPerm3("xpple"*100,"elppa"*100)))

and the result is:

Match cases

• isPerm1 = 2337999406ns
• isPerm2 = 383375133ns
• isPerm3 = 382514833ns

Mismatch cases

• isPerm1 = 29573489ns
• isPerm2 = 381622225ns
• isPerm3 = 417863227ns

As can be expected, the char counts map speeds up positive cases but can slow down negative cases (overhead on building the char counts map).