сравнивая последовательности в Ruby

Question

Предполагая, что мне нужно (от маленького до среднего) массива:

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["aaa", "bbb", "ccc"]

Как определить, содержит ли tokens все записи template в том же порядке?

(Обратите внимание, что в приведенном выше примере первый "ccc" должен игнорироваться, что приводит к совпадению из-за последнего "ccc".)

Answer 1

Это работает для ваших образцов данных.

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["aaa", "bbb", "ccc"]

pos = 0
condition_met = true
template.each do |temp|
  if (tpos = tokens[pos..-1].index temp) == nil then
    break condition_met = false
  else
    pos = tpos
  end
end

puts condition_met

Answer 2

Самый чистый, я думаю, чтобы сделать это через рекурсию:

class Array
  def align(other)
    if pos = index(other.first)
      other.size == 1 || slice(pos..-1).align(other.drop(1))
    end
  end
end

так:

[1,2,3,4,3,2,1].align([1,2,3])
=> true
[1,2,3,4,3,2,1].align([1,4,1])
=> true
[1,2,3,4,3,2,1].align([1,4,2,3])
=> nil

Answer 3

Решение, предоставленное manatwork, хорошо, но вот то, что мне кажется более рубиновым:

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["aaa", "bbb", "ccc"]

def tokens_include_template(tokens, template)
  tokens = tokens.to_enum
  template.each do |t|
    return false unless loop { break true if t == tokens.next }
  end
  true
end

puts tokens_include_template(tokens, template)

Answer 4

Это однострочник условие:

 tokens.select {|t| t if template.include?(t)}.reverse.uniq == template.reverse \
  or \
   tokens.select {|t| t if template.include?(t)}.uniq == template

Пример:

def check_order(tokens, template)
   tokens.select {|t| t if template.include?(t)}.reverse.uniq == template.reverse \
    or \
     tokens.select {|t| t if template.include?(t)}.uniq == template
end

tokens = ["aaa", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["bbb", "aaa", "ccc"]
check_order(tokens,template) # => false

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["aaa", "bbb", "ccc"]
check_order(tokens,template) # => true

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
template = ["aaa", "ccc", "bbb"]
check_order(tokens,template) # => true

Answer 5

Вот еще одна идея, если массивы от маленького до среднего, он может работать нормально.Он просто конвертирует токены в регулярное выражение и пытается сопоставить шаблон с ним.(Это также будет обрабатывать пустой шаблон, как если бы он соответствовал токенам, поэтому, если вы этого не хотите, просто явно обработайте этот угловой случай)

def tokens_in_template? tokens, *template
  re = /^#{tokens.map {|x| "(?:#{x})?"}.join}$/
  !! (template.join =~ re)
end

tokens = ["aaa", "ccc", "xxx", "bbb", "ccc", "yyy", "zzz"]
puts tokens_in_template? tokens                            # => true
puts tokens_in_template? tokens, "aaa", "bbb", "ccc"       # => true
puts tokens_in_template? tokens, "aaa", "bbb", "ccc", "aa" # => false
puts tokens_in_template? tokens, "aaa", "zzz", "ccc"       # => false
puts tokens_in_template? tokens, "aaa", "zzz"              # => true

Answer 6

Просто вычтите первый массив из второго массива, если результат пустой, у вас есть совпадение

result = template - tokens
if result.empty?
  #You have a match
else
  #No match
end

Подробнее о массивах читайте здесь http://www.ruby -doc.org / core / classes /Array.html # M000273

Если порядок важен, снова используйте оператор <=>, описанный в ссылке выше