Linear-Time Multinomial Coeffiecients

Multinomial.scala

object Combinatorics {

    /** Computes the multinomial coefficient (n; k_1, .., k_m) 
     *  where n = the sum of k_1, .., k_m.
     * 
     *  This is a variadic convenience function that allows 
     *  someone to invoke <code>multi</code> without using an 
     *  array. Note, however, that the variadic parameter is 
     *  transformed into an array when this version of 
     *  <code>multi</code> is invoked.
     * 
     *  @author Michael E. Cotterell <[email protected]>
     *  @param  k items to choose
     */
    def multi (k: Int*): Long = multi(k.toArray)

    /** Computes the multinomial coefficient (n; k_1, .., k_m) 
     *  where n = the sum of k_1, .., k_m. 
     * 
     *  This implementation requires exactly n-many 
     *  multiplications and m-many recursive calls.
     *  
     *  @see    http://michaelcotterell.com/2013/03/multinomial-coefficients/ 
     *  @author Michael E. Cotterell <[email protected]>
     *  @param  k items to choose
     */
    def multi (k: Array[Int]): Long = 
    {
        if (k.length == 1) 1L
        else {
            (1 to k.last).foldLeft(multi(k.slice(0, k.length - 1))){
                (prev, i) => prev * (k.sum - i + 1) / i
            }
        } // if
    } // multi

    /** Computes the multinomial coefficient (n; k_1, .., k_m) 
     *  where n = the sum of k_1, .., k_m.
     * 
     *  This implementation requires exactly n-many 
     *  multiplications and m-many recursive calls. Also, it is 
     *  experimentally slower than the <code>foldLeft</code> 
     *  implementation provided by the <code>multi</code> 
     *  function.
     *  
     *  @see    http://michaelcotterell.com/2013/03/multinomial-coefficients/
     *  @author Michael E. Cotterell <[email protected]>
     *  @param  k items to choose
     */
    def _multi (k: Array[Int]): Long = 
    {
        if (k.length == 1) 1L
        else {
            var product = _multi(k.slice(0, k.length-1))
            for(i <- 1 to k.last) product = product * (k.sum-i+1) / i            
            product
        } // if
    } // _multi

} // Combinatorics