Perl - 确定几个数字范围的交集

Question

我希望能够加载一长串正整数范围，并创建一个新的“摘要”范围列表，该列表是每一对范围交集的并集。而且，我想用Perl来实现这个功能。例如：

Sample ranges: (1..30) (45..90) (15..34) (92..100)

Intersection of ranges: (15..30) 

我能想到的唯一方法是使用大量嵌套的if语句来确定样本A、样本B、样本C等的起始点，并通过这种方式找出它们之间的重叠部分，但是对于每个包含大量范围的数百个样本来说，这种方法并不可行。

如果您有任何建议，我们将不胜感激！

- jake9115

---

这里有一个可能有帮助的答案：https://dev59.com/QWsz5IYBdhLWcg3whIM8 - squiguy

这对于单个坐标非常有效，但我不确定它是否实用于确定坐标范围的重叠部分。 - jake9115

这里所有范围的交集为空——(45..90)和(92..100)与(15..30)没有交集。 - hobbs

我的意思是说，如果至少有两个或更多的范围重叠，则输出相交的范围，不一定所有范围都相交。 - jake9115

Answer 1

当您需要做某件事情时，首先应该查看CPAN，看看有哪些工具可用，或者是否已经有人为您解决了问题。 Set::IntSpan和Set::IntRange是在CPAN上搜索“set”时结果的第一页。

---

你需要的是每对范围交集的并集，因此算法如下:

1. 创建一个空结果集。
2. 为每个范围创建一个集合。
3. 对于列表中的每个集合，
   1. 对于列表中的每个后续集合，
      1. 找到这两个集合的交集。
      2. 找到结果集和该交集的并集。 这是新的结果集。
4. 枚举结果集的元素。

- ikegami

---

您能详细说明或者提供一些示例代码吗？我刚接触 Perl，还不太清楚如何使用这些工具。 - jake9115

当然。你遇到了什么问题？ - ikegami

请原谅我的经验不足，但告诉我是否正确：我将使用$set = new Set::IntSpan @set_specs来创建此$set对象，使用范围的数组（存储在@set_specs中）。每个数组条目的范围应如何格式化？之后，我可以使用$i_set = intersect $set $set_spec将所有交集存储在$i_set中吗？ - jake9115

啊，你需要帮助找算法。已添加到我的答案中。 - ikegami

我理解这里的逻辑，但有一个问题：如果我有很多列表（比如说50个而不仅仅是2个），有没有一种方法可以在不使用越来越嵌套的循环的情况下完成这个任务？ - jake9115

如果你想找到每对列表的“交集”，无论如何都需要添加两个循环层。比我建议的内部循环更有效的算法是可能的。 - ikegami

Answer 2

我没有代码可以分享，但我会将每个范围扩展为哈希表，或使用Set模块，然后在集合上使用交集操作。

- Len Jaffe