有效地抓取一些符合条件的子集

Question

给定一组从 1 到 n 的连续数字，我试图找到不包含连续数字的子集的数量。

例如，对于集合 [1, 2, 3]，一些可能的子集是 [1, 2] 和 [1, 3]。前者不会被计算而后者会被计算，因为1和3不是连续的数字。

这是我的：

def f(n)
  consecutives = Array(1..n)
  stop = (n / 2.0).round
  (1..stop).flat_map { |x|
    consecutives.combination(x).select { |combo|
      consecutive = false
      combo.each_cons(2) do |l, r|
        consecutive = l.next == r
        break if consecutive
      end
      combo.length == 1 || !consecutive
    }
  }.size
end

它可以工作，但我需要它工作得更快，n <= 75 不到 12 秒。如何优化此方法，以便我可以毫不费力地处理高 n 值？

我看过：

How do I return a group of sequential numbers that might exist in an array?
Check if an array is subset of another array in Ruby

和其他一些人。我似乎找不到答案。

建议的重复项是，尽管这个问题略有不同，因为我在 Ruby 中要求进行此优化并且我不希望我的答案中出现空子集。如果我最初发现了那个问题，这个问题会非常有帮助！但是 SergGr 的回答正是我要找的。

Answer 1

设{i...n}中没有连续数的子集的个数为f(i)，则f(i)为：

1) f(i+1) ，其中没有 i 的此类子集的数量。

2) f(i+2) + 1 ，其中包含 i 的此类子集的数量（因此从子集中删除 i+1 ）

所以，

f(i)=f(i+1)+f(i+2)+1
f(n)=1
f(n-1)=2

f(1) 将是您的答案。您可以在 O(logn) 时间内使用矩阵求幂（http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html）解决它。

Answer 2

虽然@user3150716 想法是正确的，但细节是错误的。特别是你可以看到 n = 3 有 4 个子集：[1]、[2]、[3]、[1,3] 而他的公式只给出了 3 个。那是因为他错过了子集 [3]（即仅由 [i] 组成的子集）并且该错误会累积到更大的 n。另外，我认为从 1 开始比 n 更容易思考。所以正确的公式是

f(1) = 1
f(2) = 2
f(n) = f(n-1) + f(n-2) + 1

这些公式很容易使用常数 space 和 O(n) 速度中的简单循环进行编码：

def f(n)
  return 1 if n == 1
  return 2 if n == 2

  # calculate 
  # f(n) = f(n-1) + f(n - 2) + 1
  # using simple loop
  v2 = 1
  v1 = 2
  i = 3
  while i <= n do
     i += 1
     v1, v2 = v1 + v2 + 1, v1
  end 
  v1
end

你可以在网上看到这个连同原代码here

这对于任何 n <= 75 来说应该是相当快的。对于更大的 n，您可能需要一些额外的技巧，例如注意 f(n) 实际上比 Fibonacci number

少一个

f(n) = Fib(n+2) - 1

并且斐波纳契数有一个封闭公式，理论上可以更快地计算大 n。

有效地抓取一些符合条件的子集

Efficiently grab some subsets that meet criteria

ruby

algorithm

math

combinatorics