faster n choose k for combination of array ruby

Question

While trying to solve the "paths on a grid" problem, I have written the code

def paths(n, k)
  p = (1..n+k).to_a
  p.combination(n).to_a.size
end

The code works fine, for instance if n == 8 and k == 2 the code returns 45 which is the correct number of paths.

However the code is very slow when using larger numbers and I'm struggling to figure out how to quicken the process.

Answer 1

Rather than building the array of combinations just to count it, just write the function that defines the number of combinations. I'm sure there are also gems that include this and many other combinatorics functions.

Note that I am using the gem Distribution for the Math.factorial method, but that is another easy one to write. Given that, though, I'd suggest taking @stefan's answer, as it's less overhead.

def n_choose_k(n, k)
  Math.factorial(n) / (Math.factorial(k) * Math.factorial(n - k))
end

n_choose_k(10, 8)
# => 45

Note that the n and k here refer to slightly different things than in your method, but I am keeping them as it is highly standard nomenclature in combinatorics for this function.

Answer 2

def combinations(n, k)
  return 1 if k == 0 or k == n
  (k + 1 .. n).reduce(:*) / (1 .. n - k).reduce(:*)
end

combinations(8, 2)  #=> 28

Explanation about the math part

The original equation is

combinations(n, k) = n! / k!(n - k)!

Since n! / k! = (1 * 2 * ... * n) / (1 * 2 * ... * k), for any k <= n there is a (1 * 2 * ... * k) factor both in the numerator and in the denominator, so we can cancel this factor. This makes the equation become

combinations(n, k) = (k + 1) * (k + 2) * ... * (n) / (n - k)!

which is exactly what I did in my Ruby code.

Answer 3

The answers that suggest computing full factorials will generate lots of unnecessary overhead when working with big numbers. You should use the method below for calculating the binomial coefficient: n!/(k!(n-k)!)

def n_choose_k(n, k)
  return 0 if k > n
  result = 1
  1.upto(k) do |d|
    result *= n
    result /= d
    n -= 1
  end
  result
end

This will perform the minimum operations needed. Note that incrementing d while decrementing n guarantees that there will be no rounding errors. For example, {n, n+1} is guaranteed to have at least one element divisible by two, {n, n+1, n+2} is guaranteed to have at least one element divisible by three and so on.

Your code can be rewritten as:

def paths(x, y)
  # Choice of x or y for the second parameter is arbitrary
  n_choose_k(x + y, x)
end

puts paths(8, 2) # 45
puts paths(2, 8) # 45

I assume that n and k in the original version were meant to be dimensions so i labeled them x and y instead. There's no need to generate an array here.

Edit: Here is a benchmark script...

require 'distribution'

def puts_time
  $stderr.puts 'Completed in %f seconds' % (Time.now - $start_time)
  $start_time = Time.now
end

def n_choose_k(n, k)
  return 0 if k > n
  result = 1
  1.upto(k) do |d|
    result *= n
    result /= d
    n -= 1
  end
  result
end

def n_choose_k_distribution(n, k)
  Math.factorial(n) / (Math.factorial(k) * Math.factorial(n - k))
end

def n_choose_k_inject(n, k)
  (1..n).inject(:*) / ((1..k).inject(:*) * (1..n-k).inject(:*))
end

def benchmark(&callback)
  100.upto(300) do |n|
    25.upto(75) do |k|
      callback.call(n, k)
    end
  end
end

$start_time = Time.now

puts 'Distribution gem...'
benchmark { |n, k| n_choose_k_distribution(n, k) }
puts_time

puts 'Inject method...'
benchmark { |n, k| n_choose_k_inject(n, k) }
puts_time

puts 'Answer...'
benchmark { |n, k| n_choose_k(n, k) }
puts_time

Output on my system is:

Distribution gem...
Completed in 1.141804 seconds
Inject method...
Completed in 1.106018 seconds
Answer...
Completed in 0.150989 seconds