Ruby - факториал / комбинации, использующие инъекцию

Question

Я пытаюсь решить эту проблему комбинации (nCr), которая по сути сводится к факториалам. Любая помощь, объясняющая, почему мой подход не работает, полезна ..

combination = -> (n) do
    -> (r) do

    #This equation I wrote, and it doesnt work, which 
    #This seems like my equation is (n!/r!)*(n-r)!  <-- factorial equation       
    ((1..n).inject(:*)/(1..r).inject(:*)) * (1..(n - r)).inject(:*)

    # This is the answer, which seems like n!/(r!*(n-r)!)    
    #(1..n).inject(1, :*) / (((1..r).inject(1, :*)) * ((1..(n-r)).inject(1, :*)))
    end
end

n = 4
r = 2
nCr = combination.(n)
puts nCr.(r)

Answer 1

У вас есть пара проблем:

1. Вы используете неправильное уравнение для C(n,r).
2. Вы игнорируете пару граничных условий в ваших факториалах и C(n,r) реализациях.

Правильная формула для биномиального коэффициента :

             n!
C(n,r) = ----------
         r!(n - r)!

На граничных условиях.

По определению 0! - это 1, поэтому вы должны заключить свои inject в другую лямбду:

factorial = ->(n) { n == 0 ? 1 : (1..n).inject(:*) }

Кроме того, C(n,r) равно нулю, если n < r, поэтому вы должны проверить это.

combinations = ->(n, r) do
  if(n < r)
    0
  else
    factorial[n] / (factorial[r] * factorial[n - r])
  end
end

Вы также можете закорачивать корпуса n == r и r == 0 и не беспокоиться о 0!:

factorial = ->(n) { (1..n).inject(:*) }
combinations = ->(n, r) do
  if(n < r)
    0
  elsif(n == r || r == 0)
    1
  else
    factorial[n] / (factorial[r] * factorial[n - r])
  end
end

Поскольку вы явно имеете дело с комбинациями, вы, вероятно, можете спокойно игнорировать случаи n < 0 и r < 0, но вы также можете добавить проверки для них.