Как реализовать алгоритм построения строки из списка упорядоченных целых чисел?

Question

[be1ay]

Пытаюсь написать функцию которая принимает упорядоченный список целых чисел, а возвращать должна строку, в которой если больше двух чисел идут по порядку нужно заменить на сокращенную запись. Например, если на вход подать список 1,2,3,5 на выходе должно получиться 1-3,5. Но если на вход 1,2,5 то так и должно остаться 1,2,5.
Вот моя функция, но она работает правильно только для частного случая(когда последовательно идут больше 2 чисел). Как подправить или можно по другому реализовать данный алгоритм?

def myfunc(intList,k):
	if len(intList)==1:
		return str(intList[0])
	else:
		if intList[1]-intList[0]==1:
			if k==0:
				k=+1
				return str(intList[0])+'-'+str(myfunc(intList[1:],k))
			if k==1:
				return str(myfunc(intList[1:],k))
		else:
			k=0
			return str(intList[0])+','+str(myfunc(intList[1:],k))

print(myfunc([1,2,3,4,7,9,11,13,14,15,16,17,19],0))
print(myfunc([5,6,15,16],0))

Вывод:

1-4,7,9,11,13-17,19
5-6,15-16

В первом случае выводит так как надо, но это частный случай
Во втором случае видно что функция работает неправильно.

Answer 1

[Andrey K]

def fl(l):
    if len(l) > 2:
        return '%s-%s' % (l[0], l[-1])
    elif len(l) == 2:
        return '%s, %s' % (l[0], l[-1])
    else:
        return '%s' % l[0]

def cc(l):
    r = []
    b = []
    for i in l:
        if len(b) > 0:
            if i - b[-1] == 1:
                b.append(i)
            else:
                r.append(fl(b))
                b = [i]
        else:
            b.append(i)
    else:
        r.append(fl(b))

    return ', '.join(r)

Answer 2

[Валентин]

Хотите проще - держите. Логика такая: надо в список туда, где разница между двумя соседними числами > 1 вставить символ "-". А затем этот список преобразовать в строку.

def getstr(l):
    nl = [l[0],]
    for i in range(1, len(l)):
        if l[i] - nl[-1] > 1 and nl[-2] != '-':
            nl.append('-')
        nl.append(l[i])
    return nl

l = [1,2,3,4,7,9,11,13,14,15,16,17,19]
nl = getstr(l)
print(','.join(nl).replace(',-,', '-'))

Могу еще проще, но тогда вы код совсем не поймете

Comments

[be1ay]

File "C:\PrjPython\t2.py", line 12
print '.join(nl).replace(',-,', '-')
^
SyntaxError: invalid syntax
[Finished in 0.4s with exit code 1]

[Валентин]

be1ay: потому что описался. Поправил ответ.

[be1ay]

Traceback (most recent call last):
File "C:\PrjPython\t2.py", line 11, in
print(','.join(nl).replace(',-,', '-'))
TypeError: sequence item 0: expected str instance, int found
[Finished in 0.4s with exit code 1]

[be1ay]

И кстати если разница между двумя соседними числами > 1 не нужно вставлять '-', например последовательность 7,10 зачем между ними тире?

[be1ay]

Ваш алгоритм неверен вот сформированный список nl без замены ,-, на -
[1, 2, 3, 4, '-', 7, 9, '-', 11, 13, 14, 15, 16, 17, '-', 19]
видно что даже если сделать замену строка будет неправильная...
будет 1,2,3,4-7,9-11 и т.д. что неверно

[Валентин]

be1ay: очень плохо запускать код просто скопировав-и-вставив. Удачи.

[be1ay]

Очень плохо писать непроверенный код. Удачи.

Answer 3

[localghost]

Мне кажется, у Андрея отличный код, но вот еще вариант. Похож на ваш, только без рекурсии.
Просто нужно держать и начало, и конец диапазона. Ну и с последним элементом чуть особая задача - почти такая, как просто закрыть диапазон, но с небольшой поправкой. Иначе он или дублируется, или не добавляется вовсе.

def closeInt(rS, rE):
    if rE - rS == 1:
        return ", " + str(rE)
    if rE - rS > 1:
        return "-" + str(rE)
    return ""

def shortify(intlist):
    result = str(intlist[0])
    
    rangeStart = intlist[0]
    rangeEnd = intlist[0]
    for i in range(1, len(intlist)):
        if intlist[i] == intlist[i-1] + 1:
            rangeEnd += 1
        else:
            result += closeInt(rangeStart, rangeEnd)
            result += ", " + str(intlist[i])
            rangeStart = intlist[i]
            rangeEnd = intlist[i]
    
    result += closeInt(rangeStart, intlist[-1])
    return result

print(shortify([1]))
print(shortify([2,3]))
print(shortify([2,4]))
print(shortify([4,5,6]))
print(shortify([1,2,3,4,7,9,11,13,14,15,16,17,19]))
print(shortify([1,2,4,7,8,11,12,13,14,15,16,18,19]))
print(shortify([1,2,3,4,7,9,11,13,14,15,17,18,19]))

Answer 4

[some1else]

Вот рабочий код. Вся простая суть метода - заменить на 0 все номера, у которых соседи слева-справа -1 и + 1 соответственно, затем пробежаться по полученным значениям заменяя все подряд идущие 0 на '-'. Результат склеить через ',', и в завершение заменить ',-,' на '-'

from itertools import groupby

def drop_inner(nums):
    for a, b, c in zip([0, 0] + nums, [0] + nums + [0], nums + [0, 0]):
        if b:
            yield 0 if a and c and (a + 1 == b == c - 1) else b

def shorten(nums):
    return ','.join(
        str(x) if x else '-' for x, _ in groupby(drop_inner(nums))
    ).replace(',-,', '-')