S99 problem 26 Generate the combinations of K distinct objects

S9926.scala

package scalaninetynine
import scala.annotation.tailrec
import scala.collection.Iterable
import scala.collection.IndexedSeq
/*
 * S99 P6 http://aperiodic.net/phil/scala/s-99/
 * 
 * Generate the combinations of K distinct objects chosen from the N elements of a list.
 * In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. 
 * But we want to really generate all the possibilities.
 * 
 * Example:
 * 
 * scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
 * res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ... 
 *
 */
object S9926 extends App {

  class CombinationIterator[A](n: Int, ls: List[A]) extends Iterable[List[A]] {
    
    assert(n < ls.length)
    val indexedLs = ls.toIndexedSeq
    var nextComb = Vector.range(0, n)
    var nextCheck = true

    def iterator = new Iterator[List[A]] {
      def hasNext = nextCheck
      def next: List[A] = {
        val prevComb = nextComb
        val nextCombIdx = findNextIndex(prevComb,indexedLs.length - 1)
        
        if(nextCombIdx < 0) {
          nextCheck = false
          nextComb = Vector.empty
        } else {
          //increment
          val nextValAtIdx = nextComb(nextCombIdx) + 1
          val patchSize = nextComb.length - nextCombIdx
          val rangeUpperBound = nextValAtIdx + patchSize
          nextComb = nextComb.patch(nextCombIdx,Vector.range(nextValAtIdx,rangeUpperBound),patchSize)
        }
        
        prevComb.foldLeft(List[A]())((l, e) => indexedLs(e) :: l).reverse
      }
    }

    /**
     * 
     * 3, List('a, 'b, 'c, 'd, 'e, 'f) 
     *  Vector( 0,  1,  2,  3,  4,  5)
     * 
     * List('a, 'b, 'c) ----> Vector(0, 1, 2)
     *                                     ^
     * List('a, 'b, 'd) ----> Vector(0, 1, 3)
     *                                     ^
     * List('a, 'b, 'e) ----> Vector(0, 1, 4)
     *                                     ^
     * List('a, 'b, 'f) ----> Vector(0, 1, 5) Vector(2) is 5 (max) 
     *                                  ^     
     * List('a, 'c, 'd) ----> Vector(0, 2, 3) 
     *                                     ^
     * List('a, 'c, 'e) ----> Vector(0, 2, 4)
     *                                     ^
     * List('a, 'c, 'f) ----> Vector(0, 2, 5) Vector(2) is 5 (max) 
     *                                  ^
     * List('a, 'd, 'e) ----> Vector(0, 3, 4)
     *                                     ^
     * List('a, 'd, 'f) ----> Vector(0, 3, 5) Vector(2) is 5 (max)
     *                                  ^
     * List('a, 'e, 'f) ----> Vector(0, 4, 5) Vector(2) is 5 (max), Vector(1) is 4 (max)
     *                               ^ 
     * List('b, 'c, 'd) ----> Vector(1, 2, 3)
     *                                     ^
     * List('b, 'c, 'e) ----> Vector(1, 2, 4)
     *                                     ^
     * List('b, 'c, 'f) ----> Vector(1, 2, 5) Vector(2) is 5 (max) 
     *                                  ^
     * List('b, 'd, 'e) ----> Vector(1, 3, 4)
     *                                     ^
     * List('b, 'd, 'f) ----> Vector(1, 3, 5) Vector(2) is 5 (max)
     *                                  ^
     * List('b, 'e, 'f) ----> Vector(1, 4, 5) Vector(2) is 5 (max), Vector(1) is 4 (max)
     *                               ^
     * List('c, 'd, 'e) ----> Vector(2, 3, 4) 
     *                                     ^
     * List('c, 'd, 'f) ----> Vector(2, 3, 5) Vector(2) is 5 (max)
     *                                  ^
     * List('c, 'e, 'f) ----> Vector(2, 4, 5) Vector(2) is 5 (max), Vector(1) is 4 (max)
     *                               ^
     * List('d, 'e, 'f) ----> Vector(3, 4, 5) Vector(2) is 5 (max), Vector(1) is 4 (max), Vector(0) is 3 (max)
     *                        Done ^ (-1) 
     */
    private def findNextIndex(cmb: Vector[Int], max: Int): Int = {
      @tailrec
      def loop(cmb: Vector[Int], max: Int, idx: Int): Int = {
        if (cmb(idx) == max && idx == 0) {
          -1
        } else if (cmb(idx) == max) {
          loop(cmb, max - 1, idx - 1)
        } else {
          idx
        }
      }
      loop(cmb, max, cmb.length - 1);
    }
    
  }

  def combinationsBuiltin[A](n: Int, ls: List[A]): List[List[A]] = {
    ls.combinations(n).toList
  }

  combinationsBuiltin(3, List('a, 'b, 'c, 'd, 'e, 'f)).foreach{println(_)}
  
  val c = new CombinationIterator(3,List('a, 'b, 'c, 'd, 'e, 'f))
  
  c.foreach { println(_) }

}