更快n选择k组合红宝石组合

Question

在尝试解决"网格上的路径"问题时,我编写了代码

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

代码工作正常,例如if n == 8 and k == 2代码返回45正确的路径数.

但是,当使用更大的数字时代码非常慢,我正在努力弄清楚如何加快这个过程.

Answer 1

不要仅仅为了计算它而构建组合数组,而只需编写定义组合数的函数.我确信还有宝石包括这个和许多其他组合功能.

请注意,我用的宝石分配的Math.factorial方法,但那是另一种简单的一撇.但鉴于此,我建议采用@ stefan的答案,因为它的开销较小.

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

n_choose_k(10, 8)
# => 45

请注意,这里n和k这里指的是与你的方法略有不同的东西,但是我保留它们,因为它是这个函数的组合学中高度标准的命名法.

Answer 2

建议在处理大数字时计算完整阶乘会产生大量不必要的开销。您应该使用以下方法来计算二项式系数：n!/(k!(nk)!)

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

这将执行所需的最少操作。请注意，递增 d 同时递减 n 可保证不会出现舍入错误。例如，{n, n+1} 保证至少有一个元素可被二整除，{n, n+1, n+2} 保证至少有一个元素可被三整除，依此类推。

您的代码可以重写为：

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

我假设原始版本中的 n 和 k 是维度，所以我将它们标记为 x 和 y。这里不需要生成数组。

编辑：这是一个基准脚本......

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

我的系统上的输出是：

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