Combination generator ported from Java

comb.coffee

'use strict'

_ = require 'underscore'

# CombinationGenerator ported from Java.
# The algorithm is described by Kenneth H. Rosen, Discrete Mathematics and
# Its Applications, 2nd edition (NY: McGraw-Hill, 1991), pp. 284-286.
#
# Simple usage:
# combinations(["a", "b", "c", "d", "e"], 3)
# returns [["a","b","c"],["a","b","d"],["a","b","e"],["a","c","d"],["a","c","e"],["a","d","e"],["b","c","d"],["b","c","e"],["b","d","e"],["c","d","e"]]
#
class CombinationGenerator

  constructor: (@n, @r) ->
    @a = []
    @numLeft = @total = calcTotal(@n, @r)
    @reset()

  reset: ->
    @a = _.range(@r)
    @numLeft = @total

  getTotal: ->
    @total

  hasMore: ->
    @numLeft > 0

  getNext: ->
    if (@numLeft == @total)
      @numLeft--
      return @a

    i = @r - 1
    while (@a[i] == @n - @r + i)
      i--

    @a[i]++
    for j in [i + 1..@r - 1] by 1
      @a[j] = @a[i] + j - i

    @numLeft--
    @a

# n! / (r! * (n-r)!)
calcTotal = (n, r) ->
  total = 1
  total = total * (n - r + i) / i for i in [1..r] by 1
  total

# get all combinations
combinations = (arr, r) ->
  arrarr = []
  gen = new CombinationGenerator(arr.length, r)
  while(gen.hasMore())
    indices = gen.getNext()
    arrarr.push _.map(indices, (i) ->
      arr[i])
  arrarr