CODEWITHSUNDEEP
arraysalgorithmscalacombinations
tsutomu
tsutomu

Reputation: 13

How to implement generation of combinations in Array in Scala

I want Scala codes of a function that, given an array, generates k-combinations of the array.

Consider to generate 3-combinations of an array of 5 elements for example, the function, say computeNCK, behaves as follows:

computeNCK(Array(1,2,3,4,5),3) = Array(Array(1, 2, 3), Array(1, 2, 4), Array(1, 2, 5), Array(1, 3, 4), Array(1, 3, 5), Array(1, 4, 5), Array(2, 3, 4), Array(2, 3, 5), Array(2, 4, 5), Array(3, 4, 5))

The program works similarly to combinations(n: Int): Iterator[List[A]] of List, but I want deal with Array.

Note I am thinking of a code that directly handle Array, but not one that first computes in other data type like List and converts it to Array (using such as toArray).

In other words, the program is like an "Array version" of the following Scala code to compute k-combinations. 

  def computeNCK[A](l:List[A], n: Int): List[List[A]] =
    if (n > l.size) Nil
    else l match {
      case _ :: _ if n == 1 => l.map(List(_))
      case hd :: tl => computeNCK(tl, n - 1).map(hd :: _) ::: computeNCK(tl,n)
      case _ => Nil
  }

Upvotes: 0

Views: 2009

Answers (1)

pedrorijo91
pedrorijo91

Reputation: 7845

Can't you use the Array.combinations method?

scala> Array("a","b","c", "d").combinations(2).toList
res0: List[Array[String]] = List(Array(a, b), Array(a, c), Array(a, d), Array(b, c), Array(b, d), Array(c, d))

Upvotes: 1

Related Questions