arrays - 在Ruby中汇总数组元素

Question

coderbyte中的一个练习应该用来确定数组中的某些整数子集是否与数组中的最大数相加。
下面的代码似乎在我的电脑上运行，但当我在网上提交时，它似乎会导致一个无休止的循环。（无论传递的参数如何，都不会有任何输出）。

def arr_add?(arr)
  a = arr.sort
  lgst = a.pop
  size = a.size
  result = false
  while size > 1
    a.combination(size) {|c| result |= (c.inject {|r, a| r + a} == lgst)}
    size -= 1
  end
  result.to_s
end

arr_add?([1, 2, 3, 4, 10, 14])

你知道为什么会这样吗？

Answer 1

我怀疑你实际上并没有陷入一个无止境的循环，而是花了很长时间，因为你的算法效率很低。

def ArrayAdditionI(arr)
  arr_size         = arr.size
  ary              = arr.sort
  largest          = ary.pop
  ary_size         = arr_size - 1
  combination_size = ary_size
  result           = false

  while combination_size > 1
    ary.combination(combination_size) {|combination| 
      result |= (combination.inject( 
        :+
      ) == largest)
    }
    combination_size -= 1
  end
  result.to_s
end

我引入了一个新变量并重命名了一些其他变量，这样就更容易讨论算法了。我还重新格式化了它，使三个嵌套的“循环”更加明显。
让我们看看算法。
外部 while循环执行 ary_size - 1 == arr_size - 2次， combination_size范围从 2到 ary_size == arr_size - 1不等。
“循环”被执行了次，这是一个非常快速增长的数字。
最里面的“循环”（由 combination执行的操作）执行 ary_size次。
这将给出最内层操作的总执行计数：
从 combination_size到 combination.inject的总和
combination_size - 1选择 2次
arr_size - 1
在wolfram语言中，这是 choose，wolfram alpha告诉我们是 arr_size - 1，它在o（2^n）中。
稍微玩弄一下数字：
对于10个项目，我们执行了1793次 combination_size操作
对于15件商品，我们已经有98 305
20件，我们有4 456 449
在28个项目上，我们跨过了10亿个业务的门槛：1 677 721 601
对于1000个项目，我怀疑代码字节可能使用的输入大小比较合理，我们有2 670 735 203 411 771 297 463 949 434 782 054 512 824 301 493 176 042 516 553 547 843 013 099 994 928 903 285 314 296 959 198 121 926 383 029 722 247 001 218 461 778 959 624 588 092 753 669 155 960 493 619 769 880 691 017 874 939 573 116 202 845 311 796 007 113 080 079 901 646 833 889 657 798 860 899 142 814 122 011 828 559 707 931 456 870 722 063 370 635 289 362 135 539 416 628 419 173 512 766 291 969 operations. 哎呀。
尝试使用长度为5、10、15（都是瞬时的）、20（一个明显的停顿）和23、24、25的数组来体验运行时的增长速度。
假设您可以构建一个CPU，它可以在一条指令中执行内部循环。进一步假设一条指令只需要一个普朗克时间单位（即CPU的频率大约为20 000 000 000 000 000 000 000 000 000 THZ）。进一步假设可观测宇宙中的每一个粒子都是这样一个CPU。对于一个不到500个项目的数组，仍然需要比当前宇宙年龄更多的时间来执行算法。
注意，对于大多数这些编程难题，它们实际上不是编程难题，而是数学难题。它们通常需要数学洞察力，以便能够有效地解决它们。或者，在这种情况下，认识到它是 combination_size - 1，这是已知的np完全。
顺便说一句，作为一个风格问题，这里是用习惯的ruby风格编写的算法（稍微有点变化）。如您所见，在惯用的ruby中，它几乎变成了英语问题语句到代码的1:1翻译。
虽然它的渐近效率和你的算法一样低，但只要答案是 Sum[Binomial[a-1, c]*(c-1), c, 2, a-1]（与你的不同，它将继续运行，即使它已经找到一个解决方案）。（ 2^(a-2) (a-3)+1将自动为您执行此操作。）

def ArrayAdditionI(arr)
  largest = arr.delete_at(arr.index(arr.max))
  1.upto(arr.size).any? {|combination_size|
    arr.combination(combination_size).any? {|combination|
      combination.inject(:+) == largest
    }
  }.to_s
end

这是对（不清楚）问题陈述的另一种解释：

def ArrayAdditionI(arr)
  2.upto(arr.size).any? {|combination_size|
    arr.combination(combination_size).any? {|combination|
      combination.inject(:+) == arr.max
    }
  }.to_s
end