Efficiently grab some subsets that meet criteria

Question

Given a set of consecutive numbers from 1 to n, I'm trying to find the number of subsets that do not contain consecutive numbers.

E.g., for the set [1, 2, 3], some possible subsets are [1, 2] and [1, 3]. The former would not be counted while the latter would be, since 1 and 3 are not consecutive numbers.

Here is what I have:

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

It works, but I need it to work faster, under 12 seconds for n <= 75. How do I optimize this method so I can handle high n values no sweat?

I looked at:

• Check if array is an ordered subset
• 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

and some others. I can't seem to find an answer.

Suggested duplicate is Count the total number of subsets that don't have consecutive elements, although that question is slightly different as I was asking for this optimization in Ruby and I do not want the empty subset in my answer. That question would have been very helpful had I initially found that one though! But SergGr's answer is exactly what I was looking for.

Answer 1

Although @user3150716 idea is correct the details are wrong. Particularly you can see that for n = 3 there are 4 subsets: [1],[2],[3],[1,3] while his formula gives only 3. That is because he missed the subset [3] (i.e. the subset consisting of just [i]) and that error accumulates for larger n. Also I think it is easier to think if you start from 1 rather than n. So the correct formulas would be

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

Those formulas are easy to code using a simple loop in constant space and O(n) speed:

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

You can see this online together with the original code here

This should be pretty fast for any n <= 75. For much larger n you might require some additional tricks like noticing that f(n) is actually one less than a Fibonacci number

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

and there is a closed formula for Fibonacci number that theoretically can be computed faster for big n.

Answer 2

let number of subsets with no consecutive numbers from{i...n} be f(i), then f(i) is the sum of:

1) f(i+1) , the number of such subsets without i in them.

2) f(i+2) + 1 , the number of such subsets with i in them (hence leaving out i+1 from the subset)

So,

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

f(1) will be your answer. You can solve it using matrix exponentiation(http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html) in O(logn) time.