How can I check if another array is a subsequence of the other?

Question

I have two arrays; one of them, b, is probably a subset of the other, a; how can I check if b is a subsequence of a?

Basically, [3, 4, 5] would be a subsequence of (1..10).to_a, but not (1..10).to_a.shuffle.

Answer 1

a = [1,2,3]
b = (1..10).to_a

a_sorted = a.sort
b.each_cons(a.size).any?{ |c| c.sort == a_sorted }

And original solution

b.each_cons(a.size).any?{ |c| c == a }

Answer 2

Using Enumerable each consecutive to iterate

arr = [1,2,3]
(1..10).to_a.each_cons(arr.size).include? arr
# => true

arr = [1,3,2]
(1..10).to_a.each_cons(arr.size).include? arr
# => false

Answer 3

You could use Enumerable's #find_index method with each element of the potential subset and ensure that the indices are in the same order in the potential superset.

Try this:

a = (1..10).to_a
b = [3,4,5]
# Use #compact to remove all nils
b_indices = b.map {|x| a.find_index(x)}.compact
b_indices == b_indices.sort # use #sort to ensure ordering

Answer 4

Very simple and effective approach (not nil-safe):

leftovers = array.reduce(sub) { |a, e| e == a[0] ? a[1..-1] : a }
puts "sub is subsequence of array!" if leftovers.empty?

See: https://ruby-doc.org/core-2.2.0/Enumerable.html#method-i-reduce

Answer 5

You can use either Set or Array's default methods.

For Array look at it: How can I get the intersection, union, and subset of arrays in Ruby?

For Set: http://www.ruby-doc.org/stdlib-2.1.2/libdoc/set/rdoc/Set.html

Answer 6

Maybe not the most elegant solution, but should work for sure. Simple brute force:

def substring?(a, b)
  position = 0
  a.each_with_index do |v, i|
    if v == b[position] and (i + b.size - position) <= a.size
      position += 1
    elsif position == b.size
      return true
    else
      position = 0
    end
  end

  position == b.size
end

where b is your array and a is a candidate subset.

Answer 7

Here's another way. This solution conforms with my understanding of the problem, but it may not be what the asker had in mind. See my comments on the question. (Edit: upon clarification of the question, it is not what the asker wanted, but I'll leave it up for its possible educational value.)

Code

def subsequence?(a,b)
  c = b.map.with_index.to_h.values_at(*a)
  return false if c.any?(&:nil?)
  c == c.sort
end

Examples

subsequence?([3,4,5], (1..10).to_a)         #=> true
subsequence?([3,5,4], (1..10).to_a)         #=> false
subsequence?([3,4,5], (1..10).to_a.reverse) #=> false
subsequence?([3,4,5], [1,2,3,4,6])          #=> false
subsequence?([3,4,5], [3,4,2,5])            #=> true

Explanation

After computing

c = b.map.with_index.to_h.values_at(*a)

c.any?(&:nil?)

determines whether b contains all the elements of a. If it does

c == c.sort

checks to see if they are in the same order.

Example 1

a = [3,4,5]
b = (1..10).to_a

then

d = b.map.with_index.to_h
  #=> {1=>0, 2=>1, 3=>2, 4=>3, 5=>4, 6=>5, 7=>6, 8=>7, 9=>8, 10=>9}
c = d.values_at(*a)
  #=> [2, 3, 4]
c.any?(&:nil?)
  #=> false

So we see the values of a are contained in b, we need to see if they are in order:

c == c.sort
  #=> [2, 3, 4] == [2, 3, 4]
  #=> true

Example 2

a = [3,5,4]
b = (1..10).to_a

then

d = b.map.with_index.to_h
  #=> {1=>0, 2=>1, 3=>2, 4=>3, 5=>4, 6=>5, 7=>6, 8=>7, 9=>8, 10=>9}
c = d.values_at(*a)
  #=> [2, 4, 3]
c.any?(&:nil?)
  #=> false

so again we need to see if they are in order:

c == c.sort
  #=> [2, 4, 3] == [2, 3, 4]
  #=> false

Example 3

a = [3,5,4]
b = (1..10).to_a.reverse

then

d = b.map.with_index.to_h
  #=> {10=>0, 9=>1, 8=>2, 7=>3, 6=>4, 5=>5, 4=>6, 3=>7, 2=>8, 1=>9}
c = d.values_at(*a)
  #=> [7, 5, 6]
c.any?(&:nil?)
  #=> true
c == c.sort
  #=> false

Example 4

a = [3,5,4]
b = [1,2,3,4,6]

then

d = b.map.with_index.to_h
  #=> {1=>0, 2=>1, 3=>2, 4=>3, 6=>4}
c = d.values_at(*a)
  #=> [2, nil, 3]
c.any?(&:nil?) 
  #=> true

Example 5

a = [3,4,5]
b = [3,4,2,5]

then

d = b.map.with_index.to_h
  #=> {3=>0, 4=>1, 2=>2, 5=>3}
c = d.values_at(*a)
  #=> [0, 1, 3]
c.any?(&:nil?)
  #=> false
c == c.sort
  #=> true

Yet another solution

def subsequence?(a,b)
  ([a] & b.combination(a.size).to_a).any?
end

Answer 8

One more. This solution conforms with my understanding of the problem, but it may not be what the asker had in mind. See my comments on the question. (Edit: upon clarification of the question, it is not what the asker wanted, but I'll leave it up for its possible educational value.)

Code

def subsequence?(a,b)
  enum_a = a.each
  enum_b = b.each
  loop do
    av = enum_a.next
    loop do
      begin
        bv = enum_b.next
        break if (av == bv)
      rescue StopIteration
        return false
      end
    end  
  end    
  true
end 

Examples

subsequence?([3,4,5], (1..10).to_a)         #=> true
subsequence?([3,5,4], (1..10).to_a)         #=> false
subsequence?([3,4,5], (1..10).to_a.reverse) #=> false
subsequence?([3,4,5], (1..10).to_a.reverse) #=> false
subsequence?([3,4,5], [1,2,3,4,6])          #=> false
subsequence?([3,4,5], [3,4,2,5])            #=> true