如何检查一个区间是否包含另一个区间的子集？涉及IT技术相关内容。

Question

如果我有两个重叠的范围：

x = 1..10
y = 5..15

当我说：

puts x.include? y 

输出为：

false 

由于这两个范围只有部分重叠，所以返回的结果是“false”。

但如果我想让两个范围在部分重叠时返回“true”，我该怎么写呢？换句话说，我需要一种方法来判断一个范围是否包含另一个范围的子集。我想在Ruby中有一种优雅的方式来实现，但我能想到的唯一解决方案都很冗长。

- Chris

---

输出为 false 是因为以下条件是错误的：x.begin <= y and y <= x.end --- 不是因为它们只部分重叠。 - Kevin

Answer 1

高效的方法是比较极限。

(x.first <= y.last) and (y.first <= x.last)

- MarkusQ

---

为什么这比转换为数组更有效？将其转换为数组会使用大量资源吗？ - Chris

好的，这比我的好多了！ - Angela

将其转换为数组会生成一个数组并填充它的值，然后对第二个数组执行相同的操作，接着搜索这两个数组以查找匹配项。设置 x = 10000000..20000000 和 y = 30000000..40000000 并计时这两种方法，以便了解我的意思。 - MarkusQ

您可以通过扩展 Range 如此 来获得与问题中相同的调用方式，以给出 puts x.overlaps? y 并获得 true。 - davetapley

我自己思考了一下，没有想出比使用少于4个条件语句更简单的解决方案。简单最重要！ - Janko

Answer 2

使用这种方法时要小心处理大范围，但这是一种优雅的方式：

(x.to_a & y.to_a).empty?

- ski

---

这是一种O(N)的内存和时间方式，与@MarkusQ的O(1)方式不同。 - user246672

当你有时间范围而不是数字时，它并不真正可用 ;) - Janko

Answer 3

如果你正在使用Ruby 2.6版本，你可以使用Range#cover?方法与另一个Range进行比较。

(1..5).cover?(2..3)     #=> true
(1..5).cover?(0..6)     #=> false
(1..5).cover?(1...6)    #=> true

- vinibrsl

Answer 4

你也可以将这些范围转换为集合，因为你基本上在进行集合交集。如果你正在处理多个范围，这可能更容易一些。

x = (1..10).to_set
y = (5..15).to_set
!(x & y).empty? #returns true (true == overlap, false == no overlap)

- Abe Voelker

Answer 5

这种方法可以高效地测试多个范围之间的重叠：

def range_overlap?(ranges)
  sorted_ranges = ranges.sort
  sorted_ranges.each_cons(2).each do |r1, r2|
    return true if r2.first <= r1.last
  end
  return false
end


def test(r)
  puts r.inspect, range_overlap?(r)
  puts '================'
  r = r.reverse
  puts r.inspect, range_overlap?(r)
  puts '================'
end


test [[1,9], [10, 33]]
test [[1,10], [5, 8]]
test [[1,10], [10, 33]]

- Khaja Minhajuddin

---

谢谢。在我的情况下，范围是具有开始和结束日期的对象，因此覆盖方法不适用。其他方法（转换为数组）会占用太多内存。您的方法高效且快速。谢谢。 - Mauricio Moraes

Answer 6

Rails有Range#overlaps?。

def overlaps?(other)
  cover?(other.first) || other.cover?(first)
end

- Lewy

Answer 7

如果你正在检查重叠的话，我建议直接这么做：

(x.include? y.first) or (x.include? y.last)

因为一个范围必须至少包含另一个范围的一个端点。这对我来说比接受的连接答案更直观，虽然不如MarkusQ的极限比较方法高效。

- Xiong Chiamiov

---

这仅涵盖它们部分重叠的情况。假设 x = 3..6 和 y = 1..10，你的代码会返回 false，但是这两个范围确实有重叠。 - jasonkarns

Answer 8

如果一个范围包括第二个范围的开头或结尾，则它们重叠。

(x === y.first) or (x === y.last)

等同于此：

x.include?(y.first) or x.include?(y.last)

- Evgeny

---

查看我的评论，了解为什么这不是真的。 - jasonkarns

Answer 9

但是如果我想在两个范围部分重叠时使其“真实”，我该如何编写代码呢？

您可以将范围转换为数组，并使用&运算符（并集）。这将返回一个新数组，其中包含两个数组中都出现的所有元素。如果结果数组不为空，则表示存在一些重叠的元素：

def overlap?(range_1, range_2)
  !(range_1.to_a & range_2.to_a).empty?
end

- Soleone

---

这似乎是最直观的解决方案。 - Chris

@Chris -- 它可能是“最直观的”，但是1）它非常低效，2）它只适用于整数范围，所以我不建议使用它。 - MarkusQ

Answer 10

一些有用的可枚举方法：

# x is a 'subset' of y
x.all?{|n| y.include? n}
# x and y overlap
x.any?{|n| y.include? n}
# x and y do not overlap
x.none?{|n| y.include? n}
# x and y overlap one time
x.one?{|n| y.include? n}

- pguardiario