Algorithm problem in ruby: How to optimize this?

I'm trying solve one algorithm problem. The question is: You have (1..n) animals in one zoo, but some animals are enemies. The enemies are only pairs of animals, in two sets a and b. The enemies are a[i] and b[i]. For example, you have animals [1,2,3,4]we need put animals together and only sequencial animals can be put together, so you can put [1,2], [2,3], [3,4], [1,2,3], but [1,3], [1,4] or [1,3,4] cannot be put together.

n can be 1000000 (10^6)

The examples of test is

n = 4

a = [2,1,2]

b = [2,3,4] (enemies are [1,3] and [2,4], because [2,2] its valid because are the same animal)

response = 7

My generated sequence [[1], [1, 2], [1, 2, 3], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]

Example 2:

n = 5

a = [2,1,2]

b = [2,3,5] (enemies are [1,3] and [2,5], because [2,2] its valid because are the same animal)

**response = 11* *

My generated sequence: [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [2, 3, 4, 5], [3], [3, 4], [3, 4, 5], [4], [4, 5], [5]]

My code to generate sequences is below (offcourse there is more code to solve the problem, i'm sharing only the code that is slow)

def combinations(n)
  combinations = []
  elements = (1..n).to_a
  elements_sequence = (0..elements.size - 1)

  elements_sequence.each do |element1|
    elements_sequence.each do |element2|
      sliced = elements.slice(element1, element2)
      next if sliced.empty? || combinations.include?(sliced)

      combinations << sliced
    end
  end

  combinations.uniq
end

What do you recommend for this ?