Busco un formato de cadena para representar eficientemente un conjunto de índices. Por ejemplo, "1-3,6,8-10,16" produciría [1,2,3,6,8,9,10,16]

Idealmente, también podría representar secuencias infinitas.

¿Existe una forma estándar de hacer esto? O una buena biblioteca? ¿O puedes proponer tu propio formato?

¡Gracias!

Editar: ¡Guau! - Gracias por todas las respuestas bien consideradas. Estoy de acuerdo en que debería usar ':' en su lugar. ¿Alguna idea sobre listas infinitas? Estaba pensando en usar "1 .." para representar todos los números positivos.

El caso de uso es para un carrito de compras. Para algunos productos necesito restringir las ventas de productos a múltiplos de X, para otros cualquier número positivo. Entonces busco un formato de cadena para representar esto en la base de datos.

6
hoju 26 sep. 2009 a las 17:21

5 respuestas

La mejor respuesta

Si le gusta algo Pythonic, creo que 1:3,6,8:10,16 sería una mejor opción, ya que x:y es una notación estándar para el rango de índice y la sintaxis le permite usar esta notación en los objetos. Tenga en cuenta que la llamada

z[1:3,6,8:10,16]

Se traduce a

z.__getitem__((slice(1, 3, None), 6, slice(8, 10, None), 16))

Aunque este es un TypeError si z es un contenedor incorporado, puede crear la clase que devolverá algo razonable, p. Ej. como las matrices de NumPy.

También podría decir que, por convención, 5: y :5 representan rangos de índice infinitos (esto es un poco extendido ya que Python no tiene tipos incorporados con índices positivos negativos o infinitamente grandes).

Y aquí está el analizador (una hermosa línea que sufre de la falla slice(16, None, None) que se describe a continuación):

def parse(s):
    return [slice(*map(int, x.split(':'))) for x in s.split(',')]

Sin embargo, hay una trampa: 8:10 por definición incluye solo los índices 8 y 9, sin límite superior. Si eso es inaceptable para sus propósitos, ciertamente necesita un formato diferente y 1-3,6,8-10,16 me parece bien. El analizador entonces sería

def myslice(start, stop=None, step=None):
    return slice(start, (stop if stop is not None else start) + 1, step)

def parse(s):
    return [myslice(*map(int, x.split('-'))) for x in s.split(',')]

Actualización: aquí está el analizador completo para un formato combinado:

from sys import maxsize as INF

def indices(s: 'string with indices list') -> 'indices generator':
    for x in s.split(','):
        splitter = ':' if (':' in x) or (x[0] == '-') else '-'
        ix = x.split(splitter)
        start = int(ix[0]) if ix[0] is not '' else -INF
        if len(ix) == 1:
            stop = start + 1
        else:
            stop = int(ix[1]) if ix[1] is not '' else INF
        step = int(ix[2]) if len(ix) > 2 else 1
        for y in range(start, stop + (splitter == '-'), step):
            yield y

Esto también maneja números negativos, así que

 print(list(indices('-5, 1:3, 6, 8:15:2, 20-25, 18')))

Huellas dactilares

[-5, 1, 2, 6, 7, 8, 10, 12, 14, 20, 21, 22, 23, 24, 25, 18, 19]

Otra alternativa es usar ... (que Python reconoce como elipsis constante incorporada para que pueda llamar a z[...] si lo desea), pero creo que 1,...,3,6, 8,...,10,16 es menos legible.

3
ilya n. 26 sep. 2009 a las 15:19
import sys

class Sequencer(object):
    def __getitem__(self, items):
        if not isinstance(items, (tuple, list)):
            items = [items]
        for item in items:
            if isinstance(item, slice):
                for i in xrange(*item.indices(sys.maxint)):
                    yield i
            else:
                yield item


>>> s = Sequencer()
>>> print list(s[1:3,6,8:10,16])
[1, 2, 6, 8, 9, 16]

Tenga en cuenta que estoy usando el xrange incorporado para generar la secuencia. Al principio, eso parece incómodo porque no incluye el número superior de secuencias de forma predeterminada, sin embargo, resulta muy conveniente. Puedes hacer cosas como:

>>> print list(s[1:10:3,5,5,16,13:5:-1])
[1, 4, 7, 5, 5, 16, 13, 12, 11, 10, 9, 8, 7, 6]

Lo que significa que puede usar la parte step de xrange.

1
nosklo 26 sep. 2009 a las 19:28

No necesita una cadena para eso, esto es tan simple como puede ser:

from types import SliceType

class sequence(object):
    def __getitem__(self, item):
        for a in item:
            if isinstance(a, SliceType):
                i = a.start
                step = a.step if a.step else 1
                while True:
                    if a.stop and i > a.stop:
                        break
                    yield i
                    i += step
            else:
                yield a

print list(sequence()[1:3,6,8:10,16])

Salida:

[1, 2, 3, 6, 8, 9, 10, 16]

Estoy usando el poder del tipo de corte Python para expresar los rangos de secuencia. También estoy usando generadores para ser eficiente en memoria.

Tenga en cuenta que estoy agregando 1 a la parada de corte, de lo contrario los rangos serán diferentes porque la parada en cortes no está incluida.

Soporta pasos:

>>> list(sequence()[1:3,6,8:20:2])
[1, 2, 3, 6, 8, 10, 12, 14, 16, 18, 20]

Y secuencias infinitas:

sequence()[1:3,6,8:]
1, 2, 3, 6, 8, 9, 10, ...

Si tiene que darle una cadena, puede combinar @ilya n. analizador con esta solución. Extenderé @ilya n. analizador para admitir índices y rangos:

def parser(input):
    ranges = [a.split('-') for a in input.split(',')]
    return [slice(*map(int, a)) if len(a) > 1 else int(a[0]) for a in ranges]

Ahora puedes usarlo así:

>>> print list(sequence()[parser('1-3,6,8-10,16')])
[1, 2, 3, 6, 8, 9, 10, 16]
7
Nadia Alramli 26 sep. 2009 a las 14:53

Esto parecía un divertido rompecabezas para ir con mi café esta mañana. Si se conforma con su sintaxis dada (que me parece bien, con algunas notas al final), aquí hay un convertidor pyparsing que tomará su cadena de entrada y devolverá una lista de enteros:

from pyparsing import *

integer = Word(nums).setParseAction(lambda t : int(t[0]))
intrange = integer("start") + '-' + integer("end")
def validateRange(tokens):
    if tokens.from_ > tokens.to:
        raise Exception("invalid range, start must be <= end")
intrange.setParseAction(validateRange)
intrange.addParseAction(lambda t: list(range(t.start, t.end+1)))

indices = delimitedList(intrange | integer)

def mergeRanges(tokens):
    ret = set()
    for item in tokens:
        if isinstance(item,int):
            ret.add(item)
        else:
            ret += set(item)
    return sorted(ret)

indices.setParseAction(mergeRanges)

test = "1-3,6,8-10,16"
print indices.parseString(test)

Esto también se ocupa de las entradas superpuestas o duplicadas, como "3-8,4,6,3,4", y devuelve una lista de solo los enteros únicos.

El analizador se encarga de validar que rangos como "10-3" no están permitidos. Si realmente quisiera permitir esto, y hacer que algo como "1,5-3,7" devuelva 1,5,4,3,7, entonces podría ajustar las acciones de análisis intrange y mergeRanges para obtener este resultado más simple (y descartar la acción de análisis validateRange por completo).

Es muy probable que obtenga espacios en blanco en sus expresiones, supongo que esto no es significativo. "1, 2, 3-6" se manejaría igual que "1,2,3-6". Pyparsing hace esto de forma predeterminada, por lo que no ve ningún manejo especial de espacios en blanco en el código anterior (pero está allí ...)

Este analizador no maneja índices negativos, pero si eso fuera necesario también, simplemente cambie la definición de entero a:

integer = Combine(Optional('-') + Word(nums)).setParseAction(lambda t : int(t[0]))

Su ejemplo no enumeró ningún aspecto negativo, así que lo dejé fuera por ahora.

Python usa ':' para un delimitador de rango, por lo que su cadena original podría haber parecido "1: 3,6,8: 10,16", y Pascal usó '..' para los rangos de matriz, dando "1..3, 6,8..10,16 "- meh, los guiones son tan buenos en lo que a mí respecta.

1
PaulMcG 26 sep. 2009 a las 21:27

Esto es probablemente tan flojo como se puede hacer, lo que significa que estará bien incluso para listas muy grandes:

def makerange(s):
    for nums in s.split(","): # whole list comma-delimited
        range_ = nums.split("-") # number might have a dash - if not, no big deal
        start = int(range_[0])
        for i in xrange(start, start + 1 if len(range_) == 1 else int(range_[1]) + 1):
            yield i

s = "1-3,6,8-10,16"
print list(makerange(s))

Salida:

[1, 2, 3, 6, 8, 9, 10, 16]
2
Mark Rushakoff 26 sep. 2009 a las 14:18