ruby - 更快地选择k作为 ruby 阵列的组合

在尝试解决“网格上的路径”问题时，我已经编写了代码

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

该代码可以正常工作，例如if n == 8 and k == 2该代码返回45，它是正确的路径数。

但是，当使用更大的数字时，代码非常慢，而且我正在努力找出如何加快该过程的过程。

最佳答案

与其构建组合数组以对其进行计数，还不如编写定义组合数量的function。我敢肯定，还有一些包含此功能以及许多其他组合功能的 gem 。

请注意，我正在将gem Distribution用于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所指的内容与您的方法中的内容略有不同，但是我将其保留下来，因为它是此功能在组合语言中的高度标准命名法。

关于ruby - 更快地选择k作为 ruby 阵列的组合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37301649/