Преобразовать список чисел в строки

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, так что это будет совместимо с функцией диапазона, где диапазон (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]

Я предполагаю, что на самом деле нет простого / простогоспособ сделать это, но я подумал, что я хотел бы спросить здесь, прежде чем я сделаю грубый, длинный метод.

EDIT

Использование кода из ответа этот пост в качестве примера я придумал простой способ сделать первую часть.Но я думаю, что определить шаблоны для выполнения шагов будет немного сложнее.

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))

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% быстрее, чем в предыдущем топ-решении, этого оказалось достаточно:)

В любом случае, яскажем, что еще может быть место для улучшения (особенно в середине цикла).

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']. Код может быть немного очищен, но это решает вашу проблему, предполагая, что группировка может выполняться последовательно.

Answer 3

Это сравнение 3 методов. Измените объем данных и плотность с помощью значений ниже ... независимо от того, какие значения я использую, первое решение кажется мне самым быстрым. Для очень больших наборов данных третье решение становится очень медленным.

EDITED

Отредактировано, чтобы включить комментарии ниже и добавить в новое решение. Последнее решение кажется самым быстрым сейчас.

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)

Answer 4

Эта функция должна делать то, что вам нужно, без необходимости импорта.

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])