更快 n 选择 k 组合数组 ruby

Question

为了解决"paths on a grid"问题，我写了代码

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

代码工作正常，例如 if n == 8 and k == 2 代码 returns 45 这是正确的路径数。

然而，当使用较大的数字时，代码非常慢，我正在努力想出如何加快这个过程。

Answer 1

与其构建组合数组只是为了计算它，不如编写定义组合数量的 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 所指的内容与您的方法略有不同，但我保留了它们，因为它是此函数组合学中的高度标准命名法。

Answer 2

由于您对计数而不是实际组合集感兴趣，因此您应该使用 choose 函数来执行此操作。数学定义涉及评估三个不同的阶乘，但有很多取消正在进行，因此您可以通过使用范围来加快速度，以避免无论如何都会被取消的计算。

class Integer
  def choose(k)
    fail 'k > n' if k > self
    fail 'args must be positive' if k < 0 or self < 1
    return 1 if k == n || k == 0
    mm = [self - k, k].minmax
    (mm[1]+1..self).reduce(:*) / (2..mm[0]).reduce(:*)
  end
end

p 8.choose 6  # => 28

要解决您的路径问题，您可以定义

def paths(n, k)
  (n + k).choose(k)
end

p paths(8, 2)  # => 45

Answer 3

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

关于数学部分的解释

原方程为

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

因为n! / k! = (1 * 2 * ... * n) / (1 * 2 * ... * k)，对于任何k <= n，分子和分母中都有一个(1 * 2 * ... * k)因子，所以我们可以消去这个因子。这使得等式变成

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

这正是我在 Ruby 代码中所做的。

Answer 4

建议计算全阶乘的答案在处理大数时会产生大量不必要的开销。您应该使用以下方法计算二项式系数：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

这将执行所需的最少操作。请注意，在递减 n 的同时递增 d 可确保不会出现舍入错误。例如，{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

Answer 5

reduce/inject 版本不错。但是由于速度似乎有点问题，我建议使用来自@google-fail 的n_choose_k 版本。它非常有见地，建议将速度提高约 10 倍。

我建议迭代使用 k 和 ( n - k ) 中的较小者。 N-choose-K 和 N-choose-(N-K) 产生相同的结果（分母中的因式只是颠倒过来了）。所以像 52-choose-51 这样的事情可以在一次迭代中完成。

Answer 6

我通常会做以下事情：

class Integer
  def !
    (2..self).reduce(1, :*)
  end

  def choose(k)
    self.! / (k.! * (self-k).!)
  end
end

基准测试：

k = 5

Benchmark.bm do |x|
  [10, 100, 1000, 10000, 100000].each do |n|
    x.report("#{n}") { n.choose(k) }
  end
end

在我的机器上我得到：

       user     system      total        real
10  0.000008   0.000001   0.000009 (  0.000006)
100  0.000027   0.000003   0.000030 (  0.000031)
1000  0.000798   0.000094   0.000892 (  0.000893)
10000  0.045911   0.013201   0.059112 (  0.059260)
100000  4.885310   0.229735   5.115045 (  5.119902)

这不是这个星球上最快的东西，但对我来说还可以。如果它成为一个问题，那么我可以考虑优化

更快 n 选择 k 组合数组 ruby

faster n choose k for combination of array ruby

ruby

combinatorics

关于数学部分的解释