CODEWITHSUNDEEP
algorithmscala
Deepak Garg
Deepak Garg

Reputation: 159

Scala possible combinations of collection of integers

I have written following code to return all possible combinations of Array of Integers

def  findAllCombinations ( remain:Array[Int], partial:Array[Int],cum :List[Array[Int]]) : List[Array[Int]]=  {
  for ( i <- 0 until remain.size) {
    val m = partial ++ Array(remain(i))
    val n = m::cum
    findAllCombinations(remain.slice(i+1 ,remain.size),m,n)
  }
  cum
}

When I call this function using following parameters I am getting empty list.

findAllCombinations(Array(1,2,3),Array(),List(Array()))

Can somebody help me in improving the code?

Upvotes: 0

Views: 233

Answers (1)

ELinda
ELinda

Reputation: 2821

In your code, the for causes invocations of findAllCombinations but then it returns the cum that the base invocation was called with, which is List(Array()).

If you do not want permutations, but by "combinations" you mean "subsets" (i.e. get the power set of the original set):

def findAllCombinations(remain:Seq[Int]) : List[Seq[Int]]=  {
  remain match {
    case head :: tail =>
      val tailCombinations = findAllCombinations(tail)
      tailCombinations.flatMap((combo: Seq[Int]) => Seq(head +: combo, combo))
    case _ => List(Seq())
  }
}
val x = findAllCombinations(Seq(1,2,3))
println(x)
println(x.length)

Output:

List(List(1, 2, 3), List(2, 3), List(1, 3), List(3), List(1, 2), List(2), List(1), List())
8

Upvotes: 2

Related Questions