ruby - ruby 之和为N的K个数的可能方程的数量

我必须用ruby on rails创建一个程序，这样就可以减少解决特定条件所需的时间。现在我要得到k=4的响应时间越短，但是k>5的响应时间越长
问题：
问题是响应时间。
当k值大于5（k>5）时，对于下面的等式，响应时间太晚。
输入：k，n（其中0输出：和为n的k个数的可能方程的个数。

Example Input:
N=10 K=3
Example Output:
Total unique equations = 8
  1 + 1 + 8 = 10
  1 + 2 + 7 = 10
  1 + 3 + 6 = 10
  1 + 4 + 5 = 10
  2 + 2 + 6 = 10
  2 + 3 + 5 = 10
  2 + 4 + 4 = 10
  3 + 3 + 4 = 10
For reference, N=100, K=3 should have a result of 833 unique sets

这是我的ruby代码

module Combination
  module Pairs
    class Equation
      def initialize(params)
        @arr=[]
        @n = params[:n]
        @k = params[:k]
      end

      #To create possible equations
      def create_equations
        return "Please Enter value of n and k" if @k.blank? && @n.blank?
        begin
          Integer(@k)
        rescue
          return "Error: Please enter any +ve integer value of k"
        end
        begin
          Integer(@n)
        rescue
          return "Error: Please enter any +ve integer value of n"
        end
        return "Please enter k < n" if @n < @k
        create_equations_sum
      end

      def create_equations_sum
        aar = []
        @arr = []
        @list_elements=(1..@n).to_a
        (1..@k-1).each do |i|
          aar << [*0..@n-1]
        end
        traverse([], aar, 0)
        return @arr.uniq #return result
      end

      #To check sum
      def generate_sum(*args)
        new_elements = []
        total= 0
        args.flatten.each do |arg|
          total += @list_elements[arg]
          new_elements << @list_elements[arg]
        end
        if total < @n
          new_elements << @n - total
          @arr << new_elements.sort
        else
          return
        end
      end

      def innerloop(arrayOfCurrentValues)
        generate_sum(arrayOfCurrentValues)
      end

      #Recursive method to create dynamic nested loops.
      def traverse(accumulated,params, index)
        if (index==params.size)
          return innerloop(accumulated)
        end
        currentParam = params[index]
        currentParam.each do |currentElementOfCurrentParam|
          traverse(accumulated+[currentElementOfCurrentParam],params, index+1)
        end
      end
    end
  end
end

使用运行代码

params = {:n =>100, :k =>4}
c = Combination::Pairs::Equation.new(params)
c.create_equations

最佳答案

这里有两种计算答案的方法。第一种方法很简单，但效率不高；第二种方法依赖于优化技术，速度快得多，但需要大量代码。
紧凑但效率低
这是一种紧凑的计算方法，使用的方法是：
代码

def combos(n,k)
    [*(1..n-k+1)].repeated_combination(3).select { |a| a.reduce(:+) == n }
end

实例

combos(10,3)
  #=> [[1, 1, 8], [1, 2, 7], [1, 3, 6], [1, 4, 5],
  #    [2, 2, 6], [2, 3, 5], [2, 4, 4], [3, 3, 4]]

combos(100,4).size
  #=> 832

combos(1000,3).size
  #=> 83333

评论
前两次计算的时间不到一秒钟，但第三次计算需要几分钟。
效率更高，但复杂性更高
代码

def combos(n,k)
  return nil   if k.zero?
  return [n]   if k==1
  return [1]*k if k==n
  h = (1..k-1).each_with_object({}) { |i,h| h[i]=[[1]*i] }
  (2..n-k+1).each do |i|
    g = (1..[n/i,k].min).each_with_object(Hash.new {|h,k| h[k]=[]}) do |m,f|
      im = [i]*m
      mxi = m*i
      if m==k
        f[mxi].concat(im) if mxi==n
      else
        f[mxi] << im if mxi + (k-m)*(i+1) <= n
        (1..[(i-1)*(k-m), n-mxi].min).each do |j|
          h[j].each do |a|
            f[mxi+j].concat([a+im]) if
              ((a.size==k-m && mxi+j==n) ||
               (a.size<k-m && (mxi+j+(k-m-a.size)*(i+1))<=n))
          end
        end
      end
    end
    g.update({ n=>[[i]*k] }) if i*k == n
    h.update(g) { |k,ov,nv| ov+nv }
  end
  h[n]
end

实例

p combos(10,3)
  #=> [[3, 3, 4], [2, 4, 4], [2, 3, 5], [1, 4, 5],
  #    [2, 2, 6], [1, 3, 6], [1, 2, 7], [1, 1, 8]]
p combos(10,4)
  #=> [[2, 2, 3, 3], [1, 3, 3, 3], [2, 2, 2, 4], [1, 2, 3, 4], [1, 1, 4, 4],
  #    [1, 2, 2, 5], [1, 1, 3, 5], [1, 1, 2, 6], [1, 1, 1, 7]]
puts "size=#{combos(100 ,3).size}"  #=>   833
puts "size=#{combos(100 ,5).size}"  #=> 38224
puts "size=#{combos(1000,3).size}"  #=> 83333

评论
计算时间约为5秒，其余均在1秒以下。
解释
此方法使用Array#repeated_combination来计算解。状态变量是用于计算数组大小不大于combos(1000,3).size的最大正整数，其元素总和不大于k。以等于1的最大整数开头。下一步是计算包含数字1和2的n或更少元素的所有组合，然后是1、2和3，依此类推，直到我们拥有包含数字1到k的k或更少元素的所有组合。然后，我们从最后一次计算中选择n元素的所有组合。
假设

k => 3
n => 7

然后

h = (1..k-1).each_with_object({}) { |i,h| h[i]=[[1]*i] }
  #=> (1..2).each_with_object({})   { |i,h| h[i]=[[1]*i] }
  #=> { 1=>[[1]], 2=>[[1,1]] }

这将读取，仅使用数字k，n是所有和为1的数组的数组，而[[1]]是所有和为1的数组的数组。
注意，这不包括元素[[1,1]]。这是因为，已经有了2元素，如果不能与任何其他元素组合，则总和为3=>[[1,1,1]]。
我们接下来执行：

enum = (2..n-k+1).each #=> #<Enumerator: 2..5:each>

我们可以将此枚举数转换为数组，以查看它将传递到其块中的值：

enum.to_a              #=> [2, 3, 4, 5]

作为k=3您可能想知道为什么这个数组以3 < 7结尾。这是因为没有包含三个正整数的数组，其中至少有一个是an => 7或a5，其元素总和为6。
第一个值7传递到块中，块变量7表示为enum。我们现在将计算一个hashi，它包含所有数组，这些数组的总和小于或等于2，最多包含g元素，包括一个或多个n => 7，以及零个或多个k => 3。（这有点麻烦，但正如我将解释的，它仍然不精确。）

enum2 = (1..[n/i,k].min).each_with_object(Hash.new {|h,k| h[k]=[]})
  #=> (1..[7/2,3].min).each_with_object(Hash.new {|h,k| h[k]=[]})
  #=> (1..3).each_with_object(Hash.new {|h,k| h[k]=[]})

dynamic programming创建由块变量2表示的初始空散列。此哈希的默认值为：

f[k] << o

相当于

(f[k] |= []) << o

意思是如果1没有键f，

f[k] = []

在之前执行

f[k] << o

执行。
f将把以下元素传递到其块中：

enum2.to_a #=> => [[1, {}], [2, {}], [3, {}]]

（尽管当第一个元素之后的元素传递到块中时，哈希可能不是空的）。传递给块的第一个元素是k，由块变量表示：

m => 1
f => Hash.new {|h,k| h[k]=[]}

enum2意味着我们将首先构造包含一个（[1, {}]）m => 1的数组。

im = [i]*m #=> [2]*1 => [2]
mxi = m*i  #=>   2*1 =>  2

作为i=，我们接下来执行

f[mxi] << im if mxi + (k-m)*(i+1) <= n
  #=> f[2] << [2] if 2 + (3-1)*(1+1) <= 7
  #=> f[2] << [2] if 8 <= 7

这将考虑是否应将2添加到(m == k) #=> (1 == 3) => false而不添加任何整数[2]。（我们还没有考虑将一个f[2]与小于j < i = 2[即2]的整数组合）作为2，我们没有将1添加到8 <= 7。原因是，要使它成为长度[2]数组的一部分，它的形式应该是f[2]，其中k=3和[2,x,y]，所以x > 2。像泥一样干净？
下一步，

enum3 = (1..[(i-1)*(k-m), n-mxi].min).each
  #=> = (1..[2,5].min).each
  #=> = (1..2).each
  #=> #<Enumerator: 1..2:each>

它传递值

enum3.to_a #=> [1, 2]

进入它的块，由块变量y > 2表示，它是散列2+x+y >= 2+3+3 = 8 > n = 7的键。我们在这里要做的是将一个j（h）与包含整数的数组组合在一起，这些整数的总和为2（即，仅为m=1），因此得到的数组的元素的总和为1。
1不将大于j的值传递到它的块中的原因是m * i + j => 1 * 2 + j => 2 + j对于enum3是空的（但是当j时它稍微复杂一些）。
对于2

h[j]              #=> [[1]]
enum4 = h[j].each #=> #<Enumerator: [[1]]:each>
enum4.to_a        #=> [[1]]
a                 #=> [1]

所以

f[mxi+j].concat([a+im]) if
  ((a.size==k-m && mxi+j==n) || (a.size<k-m && (mxi+j+(k-m-a.size)*(i+1))<=n))
  #=> f[2+1].concat([[1]+[2]) if ((1==2 && 2+1==7) || (1<=3-1 && (2+1+(1)*(3)<=7))
  #=> f[3].concat([1,2])      if ((false && false) || (1<=2   && (6<=7))
  #=> f[3] = [] << [[1,2]]    if (false            || (true   && true)
  #=> f[3] = [[1,2]]          if true

所以左边的表达式是求值的。同样，条件表达式有点复杂。首先考虑：

a.size==k-m && mxi+j==n

相当于：

([2] + f[j]).size == k && ([2] + f[j]).reduce(:+) == n

也就是说，如果数组的h[l]元素总和为l > 2，则将其包括在内。
第二个条件考虑元素小于i > 2的数组j => 1是否可以用整数[2] + f[j]来“完成”，并且其总和是否小于k。
现在，n
我们现在将[2] + f[j]增加到k并考虑数组l > i = 2，其元素总数将n。
对于f #=> {3=>[[1, 2]]}

h[j]              #=> [[1, 1]]
enum4 = h[j].each #=> #<Enumerator: [[1, 1]]:each>
enum4.to_a        #=> [[1, 1]]
a                 #=> [1, 1]

f[mxi+j].concat([a+im]) if
  ((a.size==k-m && mxi+j==n) || (a.size<k-m && (mxi+j+(k-m-a.size)*(i+1)<=n))
  #=> f[4].concat([1, 1, 2]) if ((2==(3-1) && 2+2 == 7) || (2+2+(3-1-2)*(3)<=7))
  #=> f[4].concat([1, 1, 2]) if (true      && false)    || (false && true))
  #=> f[4].concat([1, 1, 2]) if false

因此不执行此操作（因为j和2。
我们现在将[2] + h[2]增加到4，这意味着我们将构造具有两个（j => 2=）[1,1,2].size => 3 = k的数组。

f={3=>[[1, 2]], 4=>[[2, 2]]}

当[1,1,2].reduce(:+) => 4 < 7 = n时不添加其他数组，因此我们有：

g #=> {3=>[[1, 2]], 4=>[[2, 2]]}

声明

g.update({ n=>[i]*k }) if i*k == n
  #=> g.update({ 7=>[2,2,2] }) if 6 == 7

如果元素的总和等于m，则将元素2添加到哈希i，而不是。
我们现在使用Enumerable#each_with_object（又名hash merge！）将2折叠成m => 3。：

h.update(g) { |k,ov,nv| ov+nv }
  #=> {}.update({3=>[[1, 2]], 4=>[[2, 2]]} { |k,ov,nv| ov+nv }
  #=> {1=>[[1]], 2=>[[1, 1]], 3=>[[1, 2]], 4=>[[2, 2]]}

现在7=>[2,2,2]包含的所有数组（值）的键是数组总数，由整数g和n组成，这些数组最多有g个元素，总和最多为h，不包括那些当整数大于2时不能总和为h个元素的1个数组。
执行的操作如下：

 i    m    j         f

 h #=> { 1=>[[1]], 2=>[[1,1]] }

 2    1    1   {3=>[[1, 2]]}
 2    1    2   {3=>[[1, 2]]}
 2    2    1   {3=>[[1, 2]], 4=>[[2, 2]]}
                                {3=>[[1, 2]], 4=>[[2, 2]]}
 3    1    1   {}
 3    1    2   {}
 3    1    3   {}
 3    1    4   {7=>[[2, 2, 3]]}
 3    2    1   {7=>[[2, 2, 3], [1, 3, 3]]}

 g before g.update: {7=>[[2, 2, 3], [1, 3, 3]]}
 g after  g.update: {7=>[[2, 2, 3], [1, 3, 3]]}

 h after h.update(g): {1=>[[1]],
                       2=>[[1, 1]],
                       3=>[[1, 2]],
                       4=>[[2, 2]],
                       7=>[[2, 2, 3], [1, 3, 3]]}
 4   1     1   {}
 4   1     2   {}
 4   1     3   {7=>[[1, 2, 4]]}

 g before g.update: {7=>[[1, 2, 4]]}
 g after  g.update: {7=>[[1, 2, 4]]}

 h after h.update(g): {1=>[[1]],
                       2=>[[1, 1]],
                       3=>[[1, 2]],
                       4=>[[2, 2]],
                       7=>[[2, 2, 3], [1, 3, 3], [1, 2, 4]]}
 5   1  1   {}
 5   1  2   {7=>[[1, 1, 5]]}

 g before g.update: {7=>[[1, 1, 5]]}
 g after  g.update: {7=>[[1, 1, 5]]}

 h after h.update(g): {1=>[[1]],
                       2=>[[1, 1]],
                       3=>[[1, 2]],
                       4=>[[2, 2]],
                       7=>[[2, 2, 3], [1, 3, 3], [1, 2, 4], [1, 1, 5]]}

最后，

h[n].select { |a| a.size == k }
  #=> h[7].select { |a| a.size == 3 }
  #=> [[2, 2, 3], [1, 3, 3], [1, 2, 4], [1, 1, 5]]