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.
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.