Fast array combinations

combinations.scala

// genrate all combinations of integers in range from 0 to `len`-1
// fast as fuck
def combIdxs(len: Int, k: Int): Iterator[Array[Int]] = {
  val arr = Array.range(0, k)
  arr(k-1) -= 1
  val end = k-1
  
  Iterator.continually {
    arr(end) += 1
    if (arr(end) >= len) {
      var i = end
      while (arr(i) > len-k+i && i != 0) {
        arr(i-1) += 1
        i -= 1
      }
      i = 1
      while (i <= end) {
        if (arr(i) > len-k+i)
          arr(i) = arr(i-1)+1
        i += 1
      }
    }
    if (arr(0) > len-k) null else arr
  } takeWhile (_ != null)
}

// generate all cobinations of `arr`
def combVals(arr: Array[Int], k: Int): Iterator[Array[Int]] =
  combIdxs(arr.length, k) map { idxs =>
    val n = new Array[Int](k)
    var i = 0
    while (i < k) {
      n(i) = arr(idxs(i))
      i += 1
    }
    n
  }

// combVals(1 to 20 toArray, 5)

not-so-fast.scala

// old recursive code, fast, but not fast enough

def _combinations(arr: Array[Item], k: Int) = { 
  def c(offs: Int, set: Boolean, size: Int): Seq[Array[Item]] = {
    if (size == k) {
      val n = new Array[Item](k)
      n(size-1) = arr(offs) // this is called always with set = true
      Seq(n)
    } else if (k - size >= arr.length - offs) {
      Seq.empty
    } else {
      val a = c(offs+1, true, size+1)
      val b = c(offs+1, false, size)
      val ns = a ++ b
      if (set)
        for (n <- ns) n(size-1) = arr(offs)
      ns
    }
  }
  if (k == arr.length-1) {
    for (i <- 0 until arr.length iterator) yield {
      val n = new Array[Int](k)
      System.arraycopy(arr, 0,   n, 0, i)
      System.arraycopy(arr, i+1, n, i, arr.length-i-1)
      n
    }
  } else if (k > arr.length)
    Iterator.empty
  else if (k == arr.length)
    Iterator(arr)
  else
    c(0, true, 1) ++ c(0, false, 0) iterator
}