如何进行逆“范围"，即基于一组数字创建一个紧凑的范围? [英] How to do an inverse `range`, i.e. create a compact range based on a set of numbers?

问题描述

Python 有一个 range 方法，它允许以下内容:

<预><代码>>>>范围(1, 6)[1, 2, 3, 4, 5]

我正在寻找的是相反的:获取数字列表，并返回开始和结束.

<预><代码>>>>魔法([1, 2, 3, 4, 5])[1, 5] # 注意:5，不是 6；这与`range()`不同

对于上面的示例，这很容易做到，但是是否也可以允许间隙或多个范围，以类似 PCRE 的字符串格式返回范围? 像这样:

<预><代码>>>>魔法([1, 2, 4, 5])['1-2', '4-5']>>>魔法([1, 2, 3, 4, 5])['1-5']

我正在寻找 Python 解决方案，但我也欢迎其他语言的工作示例.更重要的是找出一种优雅、高效的算法.额外问题:是否有任何编程语言为此提供了内置方法?

解决方案

一个很好的简化代码的技巧是查看排序列表的每个元素及其索引的差异:

a = [4, 2, 1, 5]a.sort()打印 [x - i for i, x in enumerate(a)]

印刷品

[1, 1, 2, 2]

每次运行相同的数字对应于a中连续的数字.我们现在可以使用 itertools.groupby() 来提取这些运行.完整代码如下:

from itertools import groupby定义子(x):返回 x[1] - x[0]a = [5, 3, 7, 4, 1, 2, 9, 10]范围 = []对于 k，在 groupby(enumerate(sorted(a)), sub) 中可迭代:rng = 列表(可迭代)如果 len(rng) == 1:s = str(rng[0][1])别的:s = "%s-%s" % (rng[0][1], rng[-1][1])range.append(s)打印范围

打印

['1-5', '7', '9-10']

Python has a range method, which allows for stuff like:

>>> range(1, 6)
[1, 2, 3, 4, 5]

What I’m looking for is kind of the opposite: take a list of numbers, and return the start and end.

>>> magic([1, 2, 3, 4, 5])
[1, 5] # note: 5, not 6; this differs from `range()`

This is easy enough to do for the above example, but is it possible to allow for gaps or multiple ranges as well, returning the range in a PCRE-like string format? Something like this:

>>> magic([1, 2, 4, 5])
['1-2', '4-5']
>>> magic([1, 2, 3, 4, 5])
['1-5']

Edit: I’m looking for a Python solution, but I welcome working examples in other languages as well. It’s more about figuring out an elegant, efficient algorithm. Bonus question: is there any programming language that has a built-in method for this?

解决方案

A nice trick to simplify the code is to look at the difference of each element of the sorted list and its index:

a = [4, 2, 1, 5]
a.sort()
print [x - i for i, x in enumerate(a)]

prints

[1, 1, 2, 2]

Each run of the same number corresponds to a run of consecutive numbers in a. We can now use itertools.groupby() to extract these runs. Here's the complete code:

from itertools import groupby

def sub(x):
    return x[1] - x[0]

a = [5, 3, 7, 4, 1, 2, 9, 10]
ranges = []
for k, iterable in groupby(enumerate(sorted(a)), sub):
     rng = list(iterable)
     if len(rng) == 1:
         s = str(rng[0][1])
     else:
         s = "%s-%s" % (rng[0][1], rng[-1][1])
     ranges.append(s)
print ranges

printing

['1-5', '7', '9-10']

这篇关于如何进行逆“范围"，即基于一组数字创建一个紧凑的范围?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！