CODEWITHSUNDEEP
scalarecursioncombinations
keerthi
keerthi

Reputation: 23

Combinations in Scala, Need help in arriving at generic code without adding new functions

I am trying to build a scala object that finds combinations for the given list. Mathematical Notation: nc3 (ncr) Example:

input : List("a", "b", "c", "d", "e", "f")

output: List(abc, abd, abe, abf, acd, ace, acf, ade, adf, aef, bcd, bce, bcf, bde, bdf, bef, cde, cdf, cef, def)

I have come up with this below object and logic however,

  1. I see that this approach is not right because i have to add more functions as my r increases and the number of functions linearly increases with r (here r being 3).

  2. All i have done is just coded the imperative style of three for loops in three functions.

  3. Is there anyway these functions can be merged so that they are functional and should not have to repeat. By this way the object works for any value of r (ncr) without the need to add new functions.

ie; i can give input of nc4, nc5 without the need to add new functions.

object combinations_functionals {

  def main(args: Array[String]): Unit = {
    val list = List("a", "b", "c", "d", "e", "f")
    println(function(list))
  }

  def function(x: List[String]): List[String] = {
    def fun(x: List[String], y: List[String]): List[String] = x match {
      case Nil => y.reverse
      case x :: xs => {
        fun(xs, function1(xs, x) ::: y)
      }
    }
    fun(x, Nil)
  }

  def function1(x: List[String], a: String): List[String] = {
    def fun1(x: List[String], y: List[String]): List[String] = x match {
      case Nil => y
      case x :: xs => {
        fun1(xs, function2(xs, a + x) ::: y)
      }
    }
    fun1(x, Nil)
  }

  def function2(x: List[String], b: String): List[String] = {
    def fun2(x: List[String], y: List[String]): List[String] = x match {
      case Nil => y
      case x :: xs => fun2(xs, b + x :: y)
    }
    fun2(x, Nil)
  }
}

Upvotes: 0

Views: 194

Answers (1)

jwvh
jwvh

Reputation: 51271

Is there a reason you don't want to use combinations?

List("a", "b", "c", "d", "e", "f").combinations(3).map(_.mkString)
// result: Iterator[String] = List(abc, abd, abe, abf, acd, ace, acf, ade, adf, aef, bcd, bce, bcf, bde, bdf, bef, cde, cdf, cef, def)

OK, so if you need to roll your own, would this work?

def combos(level: Int, lst: List[String], acc: String = ""): List[String] = {
  if (lst.isEmpty)
    Nil
  else if (level < 2)
    (acc + lst.head) :: combos(level, lst.tail, acc)
  else
    combos(level-1, lst.tail, acc + lst.head) ::: combos(level, lst.tail, acc)
}

Usage:

combos(4, List("a", "b", "c", "d", "e"))
// res0: List[String] = List(abcd, abce, abde, acde, bcde)

Upvotes: 1

Related Questions