如何在 Ruby 中使用递归进行过滤？

Question

如何在 Ruby 中使用递归进行过滤？

假设您有一个对象数组，它有一个属性，它可以有两个值之一。如果它是第一个值 - 保留对象的第一次出现，如果它是第二个值 - 保留对象的最后一次出现。举个例子：

# type can be :foo or :bar
MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)

因此，如果它是 :foo，则保留第一次出现并丢弃所有后续（直到达到 :bar），如果它是 :bar，则丢弃除最后一次出现的所有（直到你达到 :foo）

# given the initial collection looks like this:
[a, b, c, d, e, f]

# this must be the result after filtering:
[a, d, e, f]

我用迭代来解决这个问题：

initial_collection = [a, b, c, d, e, f]

initial_collection.each_with_object([initial_collection.first]) do |item, filtered_collection|
  if filtered_collection.last.type != item.type
    filtered_collection.push(item)
  elsif item.type == :bar
    filtered_collection[-1] = item
  end
end

我无法理解如何使用递归执行此操作。特别是，我不知道如何同时跟踪上一个和下一个项目。什么是递归解决方案？

Answer 1

递归必须接收一个额外的参数来跟踪当前状态，我们为此使用type。

def recursive_filter(objects, type=nil)
  return [] if objects.empty?  # Stop condition
  first = objects.shift

  if first.type == type
    recursive_filter(objects, first.type)
  else
    [first] + recursive_filter(objects, first.type)
  end
end

Answer 2

我不会认为这个问题需要递归解决方案。我建议采用以下方法。

代码

def weed(arr)
  e = [:first, :last].cycle
  first_or_last = e.next
  arr.drop(1).each_with_object([arr.first]) do |x,a|
    if attr_same_as_previous?(x, a.last)
      a[-1] = x if first_or_last == :last
    else
      first_or_last = e.next
      a << x
    end
  end
end

def attr_same_as_previous?(x, previous)
  x[:type] == previous[:type]
end

方法attr_same_as_previous?隔离了判断给定属性是否发生变化的属性，使解决方案更加健壮。

例子

#1

MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)
g = MyObject.new(7, :bar)

arr = [a,b,c,d,e,f,g]
  #=> [#<struct MyObject id=1, type=:foo>, #<struct MyObject id=2, type=:foo>,
  #    #<struct MyObject id=3, type=:bar>, #<struct MyObject id=4, type=:bar>,
  #    #<struct MyObject id=5, type=:foo>, #<struct MyObject id=6, type=:bar>]       

weed arr
  #=> [#<struct MyObject id=1, type=:foo>,
  #    #<struct MyObject id=4, type=:bar>,
  #    #<struct MyObject id=5, type=:foo>,
  #    #<struct MyObject id=7, type=:bar>]

#2

MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :cat)
b = MyObject.new(2, :cat)
c = MyObject.new(3, :dog)
d = MyObject.new(4, :dog)
e = MyObject.new(5, :pig)
f = MyObject.new(6, :owl)
g = MyObject.new(7, :owl)

weed [a,b,c,d,e,f,g]
  #=> [#<struct MyObject id=1, type=:cat>,
  #    #<struct MyObject id=4, type=:dog>,
  #    #<struct MyObject id=5, type=:pig>,
  #    #<struct MyObject id=7, type=:owl>]

Answer 3

处理:foo需要知道前一个元素，而处理:bar需要知道下一个；所以在递归的任何给定点，我们必须查看一个三元素 window，我们可以从中将中间元素添加到我们的结果中。

这是一些模式匹配伪代码（null 表示 window 的单元格中没有元素，_ 匹配任何内容；请注意匹配案例的顺序很重要） :

f([:foo, :foo, _]) ->
  f(next_window)

f([_, :foo, _]) ->
  [middle_element] + f(next_window)

f([_, :bar, :bar]) ->
  f(next_window)

f([_, :bar, _]) ->
  [middle_element] + f(next_window)

// End of list
f([_, null, null]) ->
  []

这是一个 Ruby 版本：

def f(list, middle_index)
  window = get_window(list, middle_index)

  if window[0,2] == [:foo, :foo]
    f(list, middle_index + 1)

  elsif window[1] == :foo
    [list[middle_index]] +
    f(list, middle_index + 1)

  elsif window[1,2] == [:bar, :bar]
    f(list, middle_index + 1)

  elsif window[1] == :bar
    [list[middle_index]] +
    f(list, middle_index + 1)

  # End of list
  elsif window[1,2] == [nil, nil]
    []
  end
end

def get_window(list, middle_index)
  [maybe_type(list, middle_index - 1),
   maybe_type(list, middle_index),
   maybe_type(list, middle_index + 1)]
end

def maybe_type(list, index)
  if index < 0 or list[index].nil?
    nil
  else
    list[index].type
  end
end

输出：

MyObject = Struct.new(:id, :type)

a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)
g = MyObject.new(7, :bar)

arr = [a,b,c,d,e,f,g]

puts f(arr, 0).inspect
# [#<struct MyObject id=1, type=:foo>,
#  #<struct MyObject id=4, type=:bar>,
#  #<struct MyObject id=5, type=:foo>,
#  #<struct MyObject id=7, type=:bar>]

Answer 4

下面是递归的解法。如果您将它与我的其他答案进行比较，您会发现它是一个 假递归 ，一种伪装成递归的顺序方法。这是由于问题的性质。

def weed(arr)
  return [] if arr.empty?
  e, *rest = arr
  recurse(rest, [e], :first)
end

def recurse(arr, build, first_or_last)
  e, *rest = arr
  if e[:type] == build.last[:type]
    (build[-1] = e) if first_or_last == :last
  else
    first_or_last = (first_or_last == :first ? :last : :first)
    build << e
  end
  rest.empty? ? build : recurse(rest, build, first_or_last)
end

MyObject = Struct.new(:id, :type)
a = MyObject.new(1, :foo)
b = MyObject.new(2, :foo)
c = MyObject.new(3, :bar)
d = MyObject.new(4, :bar)
e = MyObject.new(5, :foo)
f = MyObject.new(6, :bar)
g = MyObject.new(7, :bar)

arr = [a,b,c,d,e,f,g]
  #=> [#<struct MyObject id=1, type=:foo>, #<struct MyObject id=2, type=:foo>,
  #    #<struct MyObject id=3,  type=:bar>, #<struct MyObject id=4, type=:bar>,
  #    #<struct MyObject id=5, type=:foo>, #<struct MyObject id=6, type=:bar>,
  #    #<struct MyObject id=7, type=:bar>]

weed arr
  #  [#<struct MyObject id=1, type=:foo>,
  #   #<struct MyObject id=4, type=:bar>,
  #   #<struct MyObject id=5, type=:foo>,
  #   #<struct MyObject id=7, type=:bar>]

如何在 Ruby 中使用递归进行过滤？

How to filter with recursion in Ruby?

ruby

recursion

tail-recursion