将数字列表转换为字符串范围

Question

我想知道是否有一种简单（或已经创建好的）方法来实现这个的相反操作：从连字符和逗号生成数字列表。 可以使用此链接执行以下操作：

>> list(hyphen_range('1-9,12,15-20,23'))
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 19, 20, 23]:

我希望做相反的事情（请注意，10和21也包括在内，这样它就可以与range函数兼容，其中range(1,10)=[1,2,3,4,5,6,7,8,9]）：

>> list_to_ranges([1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 15, 16, 17, 18, 19, 20, 23])
'1-10,12,15-21,23'

最终，我希望输出还能包括一步，即输出的最后一个数字表示该步骤：

>> list_to_ranges([1, 3, 5, 7, 8, 9, 10, 11])
'1-13:2,8,10'

基本上，这就像是一个“反向”的范围函数。

>> tmp = list_to_ranges([1, 3, 5])
>> print tmp
'1-7:2'
>> range(1, 7, 2)
[1, 3, 5]

我的猜测是，没有真正简单/容易的方法来做到这一点，但在我采取某些蛮力、冗长的方法之前，我想在这里问一下。

编辑

使用此帖子中的答案代码作为示例，我想出了一个简单的方法来完成第一部分。但我认为识别模式以执行步骤可能会更难一些。

from itertools import groupby
from operator import itemgetter

data = [ 1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28]
print data, '\n'

str_list = []
for k, g in groupby(enumerate(data), lambda (i,x):i-x):
   ilist = map(itemgetter(1), g)
   print ilist
   if len(ilist) > 1:
      str_list.append('%d-%d' % (ilist[0], ilist[-1]+1))
   else:
      str_list.append('%d' % ilist[0])
print '\n', ','.join(str_list)

编辑2

以下是我尝试包含步长的方法...它非常接近，但是前面的数字会重复。我认为稍微调整一下就可以接近我想要的结果-或者至少足够好了。

import numpy as np
from itertools import groupby

def list_to_ranges(data):
   data = sorted(data)
   diff_data = np.diff(data).tolist()
   ranges = []
   i = 0
   for k, iterable in groupby(diff_data, None):
      rng = list(iterable)
      step = rng[0]
      if len(rng) == 1:
         ranges.append('%d' % data[i])
      elif step == 1:
         ranges.append('%d-%d' % (data[i], data[i+len(rng)]+step))
      else:
         ranges.append('%d-%d:%d' % (data[i], data[i+len(rng)]+step, step))
      i += len(rng)
   return ','.join(ranges)

data = [1, 3, 5, 6, 7, 11, 13, 15, 16, 17, 18, 19, 22, 25, 28]
print data
data_str = list_to_ranges(data)
print data_str

_list = []
for r in data_str.replace('-',':').split(','):
   r = [int(a) for a in r.split(':')]
   if len(r) == 1:
      _list.extend(r)
   elif len(r) == 2:
      _list.extend(range(r[0], r[1]))
   else:
      _list.extend(range(r[0], r[1], r[2]))
print _list
print list(set(_list))

- Scott B

---

你所说的暴力破解方法，不一定非常冗长。 - Milo Wielondek

我同意。为了识别模式，特别是如果您还想添加非单位步骤识别，您将不得不解析列表。 - Joel Cornett

这里存在一些歧义：1-13:2,8,10与1-7:2,7-11是相同的。在我们真正考虑一种算法之前，您需要更精确地定义您想要的内容。 - Winston Ewert

@Winston Ewert：同意。这是我考虑过的事情...任何一个都是有效的输出。我并不在乎哪个结果发生，只要它们是等价的。 - Scott B

好的，但是1,3,5,7,8,9,10,11也是等价的，1,3,5,7-11也是等价的。你肯定有某种超越等价的要求。 - Winston Ewert

@Winston Ewert：我猜我的“想法”标准是，我希望列表尽可能短...当数据混合时，这变得非常困难。例如：1,3,5,7,8,9,10,11,13,15 理想情况下应该变成 1-17:2,8,10。但到目前为止，我只是从左到右工作，并在当前模式/连续中断时停止（请参见我的“编辑2”）。 - Scott B

Answer 1

一种方法是逐个“吃掉”输入序列并存储部分范围的结果，直到你获得了所有结果：

def formatter(start, end, step):
    return '{}-{}:{}'.format(start, end, step)
    # return '{}-{}:{}'.format(start, end + step, step)

def helper(lst):
    if len(lst) == 1:
        return str(lst[0]), []
    if len(lst) == 2:
        return ','.join(map(str,lst)), []

    step = lst[1] - lst[0]
    for i,x,y in zip(itertools.count(1), lst[1:], lst[2:]):
        if y-x != step:
            if i > 1:
                return formatter(lst[0], lst[i], step), lst[i+1:]
            else:
                return str(lst[0]), lst[1:]
    return formatter(lst[0], lst[-1], step), []

def re_range(lst):
    result = []
    while lst:
        partial,lst = helper(lst)
        result.append(partial)
    return ','.join(result)

我用一系列单元测试来测试它，并且所有的测试都通过了。它也可以处理负数，但它们看起来会有些丑陋（这其实不是谁的错）。

示例：

>>> re_range([1,  4,5,6, 10, 15,16,17,18, 22, 25,26,27,28])
'1,4-6:1,10,15-18:1,22,25-28:1'
>>> re_range([1, 3, 5, 7, 8, 9, 10, 11, 13, 15, 17])
'1-7:2,8-11:1,13-17:2'

注意：我编写的代码适用于Python 3。

---

性能

上面的解决方案没有进行任何性能优化。特别是，每次使用切片重新构建列表时，如果输入列表具有特定形状，可能需要花费一些时间。因此，第一个简单的改进是在可能的情况下使用itertools.islice()。

无论如何，这里是相同算法的另一种实现，它使用scan索引扫描输入列表，而不是使用切片:

def re_range(lst):
    n = len(lst)
    result = []
    scan = 0
    while n - scan > 2:
        step = lst[scan + 1] - lst[scan]
        if lst[scan + 2] - lst[scan + 1] != step:
            result.append(str(lst[scan]))
            scan += 1
            continue

        for j in range(scan+2, n-1):
            if lst[j+1] - lst[j] != step:
                result.append(formatter(lst[scan], lst[j], step))
                scan = j+1
                break
        else:
            result.append(formatter(lst[scan], lst[-1], step))
            return ','.join(result)

    if n - scan == 1:
        result.append(str(lst[scan]))
    elif n - scan == 2:
        result.append(','.join(map(str, lst[scan:])))

    return ','.join(result)

当它比之前的最佳解决方案快了约65%时，我停止了对它的工作，这似乎已经足够了:)

无论如何，我认为仍然可能有改进的空间（特别是在中间的for循环中）。

- Rik Poggi

---

也非常适用于我的测试，谢谢。我唯一改变的是在辅助函数的中间项中添加了步骤（范围不包括第二个项，即：range(1,6)=[1,2,3,4,5] -> 它不包括6）。所以对于您的第一个示例，而不是4-6:1，它应该是4-7:1。因此使用....format(lst[0], lst[i]+step, step)，等等... - Scott B

@ScottB：我没有注意到你需要那种行为。我认为这是一种品味问题，例如，我不喜欢连字符字符串显示最后一个数字，而应该由“hypend_range”来修复它的行为，就像区间一样（仅作为示例）。我将把你的修复作为自定义的“formatter”添加 :) - Rik Poggi

@ScottB：我认为这很慢，因为输入列表被递归和重复切割了。你是真的有性能问题还是只是在进行基准测试？更好的方法是做同样的事情，但是不使用递归和切割来解析字符串，我会考虑代码...（同时，如果你想分享你的基准测试环境，我很乐意与之合作，而不是要建立一个新的环境）。 - Rik Poggi

是的，我只是在做一些基准测试，看看这两个解决方案如何扩展。由于你的解决方案执行了所有递归，所以我想当数字列表很大时，它会变得很慢。实际上，我有一个修改过的版本（来自“EDIT 2”），似乎始终是最快的。我喜欢你的解决方案的一个原因是它通常似乎比Kaidence的结果更短，但我的修改方法给出与你的相同的结果，但即使对于非常大量的数据也能快速完成。我将很快发布我的比较作为新答案... - Scott B

我发布了每种方法的比较。 - Scott B

Answer 2

这个很可能是您正在寻找的内容。

编辑：我看到您已经找到了这篇文章。对此我深表歉意。

为了帮助你完成第二部分，我自己也尝试了一下。以下是我的成果：

from numpy import diff

data = [ 1, 3, 5, 7, 8, 9, 10, 11, 13, 15, 17 ]
onediff, twodiff = diff(data), diff(diff(data))
increments, breakingindices = [], []
for i in range(len(twodiff)):
    if twodiff[i] != 0:
        breakingindices.append(i+2) # Correct index because of the two diffs
        increments.append(onediff[i]) # Record the increment for this section

# Increments and breakingindices should be the same size
str_list = []
start = data[0]
for i in range(len(breakingindices)):
    str_list.append("%d-%d:%d" % (start, data[breakingindices[i]-1], increments[i]))
    start = data[breakingindices[i]]
str_list.append("%d-%d:%d" % (start, data[len(data)-1], onediff[len(onediff)-1]))
print str_list

给定输入列表，这会给出：['1-7:2', '8-11:1', '13-17:2']。代码需要进行一些清理，但是假设可以按顺序完成分组，则可以解决您的问题。

{注意：对于[1,2,3,5,6,7]，此代码将返回['1-3:1'，'5-5:2'，'6-7:1']而不是['1-3:1'，'5-7:1']}

- Jos Kraaijeveld

---

是的，太好了...顺便说一下，这基本上就是我刚刚发现的东西（请参见我的编辑）。你知道有什么简单的方法可以使用步骤吗？ - Scott B

请不要只发布一个链接作为答案。要么在您的帖子中提供链接中的信息，要么将其作为评论提供。 - agf

@ScottB，我刚刚更新了我的回答帖子并进行了更多的澄清。 - Jos Kraaijeveld

很高兴听到这个好消息 :) 祝你好运！ - Jos Kraaijeveld

似乎我使用了我“EDIT 2”帖子的修改方法可以得到最佳结果。我制作了一个新答案来比较每个解决方案（我的，你的和Rik的）。 - Scott B

Answer 3

这是三种方法的比较。通过下面的值来改变数据量和密度...无论我使用什么值，第一种解决方案似乎对我来说都是最快的。对于非常大的数据集，第三种解决方案变得非常慢。

编辑

根据下面的评论进行编辑，并添加一个新的解决方案。现在最后一个解决方案似乎是最快的。

import numpy as np
import itertools
import random
import timeit

# --- My Solution --------------------------------------------------------------
def list_to_ranges1(data):
   data = sorted(data)
   diff_data = np.diff(data)
   ranges = []
   i = 0
   skip_next = False
   for k, iterable in itertools.groupby(diff_data, None):
      rng = list(iterable)
      step = rng[0]
      if skip_next:
         skip_next = False
         rng.pop()

      if len(rng) == 0:
         continue
      elif len(rng) == 1:
         ranges.append('%d' % data[i])
      elif step == 1:
         ranges.append('%d-%d' % (data[i], data[i+len(rng)]+step))
         i += 1
         skip_next = True
      else:
         ranges.append('%d-%d:%d' % (data[i], data[i+len(rng)]+step, step))
         i += 1
         skip_next = True
      i += len(rng)

   if len(rng) == 0 or len(rng) == 1:
      ranges.append('%d' % data[i])
   return ','.join(ranges)

# --- Kaidence Solution --------------------------------------------------------
# With a minor edit for use in range function
def list_to_ranges2(data):
   onediff = np.diff(data)
   twodiff = np.diff(onediff)
   increments, breakingindices = [], []
   for i in range(len(twodiff)):
       if twodiff[i] != 0:
           breakingindices.append(i+2)  # Correct index because of the two diffs
           increments.append(onediff[i]) # Record the increment for this section

  # Increments and breakingindices should be the same size
   str_list = []
   start = data[0]
   for i in range(len(breakingindices)):
       str_list.append("%d-%d:%d" % (start,
                                     data[breakingindices[i]-1] + increments[i],
                                     increments[i]))
       start = data[breakingindices[i]]
   str_list.append("%d-%d:%d" % (start,
                                 data[len(data)-1] + onediff[len(onediff)-1],
                                 onediff[len(onediff)-1]))
   return ','.join(str_list)

# --- Rik Poggi Solution -------------------------------------------------------
# With a minor edit for use in range function
def helper(lst):
    if len(lst) == 1:
        return str(lst[0]), []
    if len(lst) == 2:
        return ','.join(map(str,lst)), []

    step = lst[1] - lst[0]
    #for i,x,y in itertools.izip(itertools.count(1), lst[1:], lst[2:]):
    for i,x,y in itertools.izip(itertools.count(1),
                                itertools.islice(lst, 1, None, 1),
                                itertools.islice(lst, 2, None, 1)):
        if y-x != step:
            if i > 1:
                return '{}-{}:{}'.format(lst[0], lst[i]+step, step), lst[i+1:]
            else:
                return str(lst[0]), lst[1:]
    return '{}-{}:{}'.format(lst[0], lst[-1]+step, step), []

def list_to_ranges3(lst):
    result = []
    while lst:
        partial,lst = helper(lst)
        result.append(partial)
    return ','.join(result)

# --- Rik Poggi Solution 2 -----------------------------------------------------
def formatter(start, end, step):
    #return '{}-{}:{}'.format(start, end, step)
    return '{}-{}:{}'.format(start, end + step, step)

def list_to_ranges4(lst):
    n = len(lst)
    result = []
    scan = 0
    while n - scan > 2:
        step = lst[scan + 1] - lst[scan]
        if lst[scan + 2] - lst[scan + 1] != step:
            result.append(str(lst[scan]))
            scan += 1
            continue

        for j in xrange(scan+2, n-1):
            if lst[j+1] - lst[j] != step:
                result.append(formatter(lst[scan], lst[j], step))
                scan = j+1
                break
        else:
            result.append(formatter(lst[scan], lst[-1], step))
            return ','.join(result)

    if n - scan == 1:
        result.append(str(lst[scan]))
    elif n - scan == 2:
        result.append(','.join(itertools.imap(str, lst[scan:])))

    return ','.join(result)

# --- Test Function ------------------------------------------------------------
def test_data(data, f_to_test):
   data_str = f_to_test(data)
   _list = []
   for r in data_str.replace('-',':').split(','):
      r = [int(a) for a in r.split(':')]
      if len(r) == 1:
         _list.extend(r)
      elif len(r) == 2:
         _list.extend(range(r[0], r[1]))
      else:
         _list.extend(range(r[0], r[1], r[2]))
   return _list

# --- Timing Tests -------------------------------------------------------------
# Generate some sample data...
data_list = []
for i in range(5):
   # Note: using the "4000" and "5000" values below, the relative density of
   # the data can be changed.  This has a huge effect on the results
   # (particularly on the results for list_to_ranges3 which uses recursion).
   data_list.append(sorted(list(set([random.randint(1,4000) for a in \
                                      range(random.randint(5,5000))]))))

testfuncs = list_to_ranges1, list_to_ranges2, list_to_ranges3, list_to_ranges4
for f in testfuncs:
   print '\n', f.__name__
   for i, data in enumerate(data_list):
      t = timeit.Timer('f(data)', 'from __main__ import data, f')
      #print f(data)
      print i, data==test_data(data, f), round(t.timeit(200), 3)

- Scott B

---

正如我在答案中所说，我编写的是Python 3代码，这意味着如果你想在Python 2下运行它，你将不得不使用izip()，imap()和xrange()。或者你可以在你的print周围加上几个括号，并用python3运行它（这就是我所做的）。 - Rik Poggi

另一个容易应用的改进是使用zip(count(1), islice(lst, 1, None, 1), islice(lst, 2, None, 1))，而不是每次都用lst[1：]和lst[2：]构建新列表。无论如何，我会想出一些真正改进我的代码的方法。 - Rik Poggi

没错，我已经做出了更改，但即使有这些更改，我仍然发现对于大量数字的列表来说，第三种方法仍然是最慢的。 - Scott B

是的，将其更改为f(data)会更合适，因为您将能够进行相对比较（也称为使用％）。我没有使用任何formatter模块，formatter是我在答案开头定义的函数。因此，SO已自动将对话移至聊天室这里。如果您愿意，我们可以在那里继续。 - Rik Poggi

你仍在使用range()，**在Python 2中，你必须使用xrange()**。我真的不想听起来像在吹嘘，但是如果你这样做，你会发现我的更快，即使对于更大的数据集。（为了测试性能，你应该在实际应用程序中进行测试） - Rik Poggi

Answer 4

这类版本与此处处理步长为1的情况类似，但也处理单例（序列中不超过2个元素或重复元素）和非单位步长（包括负步长）。它还不会删除像[1, 2, 3, 3, 4, 5]这样的列表中的重复项。

至于运行时间：在你眨眼之前就完成了。

def ranges(L):
    """return a list of singletons or ranges of integers, (first, last, step)
    as they occur sequentially in the list of integers, L.

    Examples
    ========

    >>> list(ranges([1, 2, 4, 6, 7, 8, 10, 12, 13]))
    [1, (2, 6, 2), 7, (8, 12, 2), 13]
    >>> list(ranges([1,2,3,4,3,2,1,3,5,7,11,1,2,3]))
    [(1, 4, 1), (3, 1, -1), (3, 7, 2), 11, (1, 3, 1)]

    """
    if not L:
        return []
    r = []
    for i in L:
        if len(r) < 2:
            r.append(i)
            if len(r) == 2:
                d = r[1] - r[0]
        else:
            if i - r[1] == d:
                r[1] = i
            else:
                if r[1] - r[0] == d:
                    yield(r.pop(0))
                    r.append(i)
                    d = r[1] - r[0]
                else:
                    yield(tuple(r+[d]))
                    r[:] = [i]
    if len(r) == 1:
        yield(r.pop())
    elif r[1] - r[0] == d:
        for i in r:
            yield i
    else:
        yield(tuple(r+[d]))

原始输出可以根据需要进行修改，例如可以创建实际的range实例。

def sranges(i):
    """return pretty string for output of ranges.

    Examples
    ========

    >>> sranges([1,2,4,6,7,8,10,12,13,15,16,17])
    '1, range(2, 8, 2), 7, range(8, 14, 2), 13, range(15, 18)'

    """
    out = []
    for i in ranges(i):
        if type(i) is int:
            out.append(str(i))
        elif i[-1] == 1:
            if i[0] == 0:
                out.append('range(%s)'%(i[1] + 1))
            else:
                out.append('range(%s, %s)'%(i[0], i[1] + 1))
        else:
            out.append('range(%s, %s, %s)'%(i[0], i[1] + i[2], i[2]))
    return ', '.join(out)

- smichr

Answer 5

这个函数应该可以满足你的需求，而且不需要任何导入。

def listToRanges(self, intList):
    ret = []
    for val in sorted(intList):
        if not ret or ret[-1][-1]+1 != val:
            ret.append([val])
        else:
            ret[-1].append(val)
    return ",".join([str(x[0]) if len(x)==1 else str(x[0])+"-"+str(x[-1]) for x in ret])

- mickayz