在Ruby中比较序列

Question

假设我有两个小到中等大小的数组：

假设我有两个小到中等大小的数组：

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

我该怎样确定tokens中是否包含了template中所有的条目，并且顺序相同？

（注意，在上面的示例中，第一个“ccc”应该被忽略，因为最后一个“ccc”是匹配的。）

- anon

---

你的问题不够明确。你说“按照相同的顺序？”然后又说“第一个‘ccc’应该被忽略，因为最后一个‘ccc’导致匹配。”所以顺序是否重要？我已经为两种情况给出了非常简单的答案。 - jamesc

好问题 +1，看看我的答案中的一行条件来检查你的数据。 - Emiliano Poggi

抱歉对于不明确的表述，顺序确实很重要-但是，第一个“ccc”并不重要，因为它不符合模板的顺序（而第二个“ccc”是）。所以我想说明的是重复可能会造成混乱。 - anon

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

- manatwork

---

你可以删除 else 部分并使用 if (pos = tokens[pos..-1].index temp) == nil then。 - thorsten müller

@thorsten müller，你是对的。我忘记了在重构条件后的事情。 - manatwork

这相当聪明，而且似乎也起作用（将编写一些单元测试来确认）-非常感谢！ - anon

太复杂了，只需将一个数组减去另一个数组即可。简单得多。 - jamesc

jamesw：减去数组时不考虑顺序。 - anon

Answer 2

这是一个一行条件：

 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

- Emiliano Poggi

---

这会针对原始数据返回false，但应该返回true。 - manatwork

谢谢 - 然而，虽然这通过了我的当前测试，但“reverse”表明存在危险的假设。实际上，如果我的原始“template”变成了["aaa", "ccc", "bbb"]，那么这将不再返回预期的值（true）。 - anon

抱歉，您的问题表述不够清晰。您说“第一个‘ccc’应该被忽略”，我认为仅最后一次出现在标记顺序中才是相关的。 - Emiliano Poggi

确实，我似乎无法让它失败 - 这让我感到有些困惑。我需要深入挖掘，提出一些更复杂的测试用例（仍然持怀疑态度，不幸的是）。在此期间，谢谢您并点赞！ - anon

你提到的情况应该返回 true，因为模板 sequence 包含在 tokens 中（对我来说它看起来并不凌乱，但我理解这可能是由于上下文 - 也许可以这样想：句子 tokens 是否包含序列 template，允许中间有任意数量的 tokens）。 - anon

Answer 3

manatwork提供的解决方案很不错，但这里有一个对我来说更像Ruby的解决方案：

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)

- Victor Deryagin

---

坦白说，我觉得这个比较难理解 - 但这可能是个人偏好的问题。不过还是谢谢你，我会考虑的。 - anon

Answer 4

我认为最干净的做法是通过递归来实现：

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

- glenn mcdonald

---

我喜欢这个！它与manatwork的解决方案相似，但更为简洁。然而它似乎不能通过我的测试用例，所以需要进一步调查... - anon

一个不通过的测试用例是什么？ - glenn mcdonald

没关系，我当时有点傻（将你的代码重写为独立函数，因为如果不必要，我不喜欢扩展数组）- 所以它似乎很好用，而且既然这是我最喜欢的解决方案，我已经接受了它。 - anon

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

- sinjed

---

事实上，我的一个同事也建议使用正则表达式，这是有效的，因为每个标记都有（或者在这个例子中，有效地构成）唯一的ID：source = tokens.map { |t| "-#{t.id}-" }.join(""); pattern = template.map { |t| "-#{t.id}-" }.join(".*"); pattern = Regexp.new(pattern); return pattern.match(source)（不幸的是，由于 Stack Overflow 的限制，我无法将其放入适当的答案中）。 - anon

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

如果顺序很重要，则使用上面链接中再次描述的<=>运算符

- jamesc

---

哎呀！你说得对。我把问题理解成顺序无关紧要了。 - jamesc

但是注释说这不是真的。注释明确指出，即使“ccc”顺序错误，数组仍应匹配！问题含糊不清，需要澄清，但我已经为两种情况提供了解决方案，那么为什么要投反对票？ - jamesc

第一个“ccc”不重要，因为有第二个。但是是的，问题需要澄清。附注：我没有投反对票。 - Victor Deryagin

这太令人困惑了 :) 没关系 @Victor Deryagin - jamesc

我已经（希望）在上面澄清了顺序很重要的问题。 - anon