3

Dado un arreglo de cadenas, toma una cadena en la entrada, que representa un polinomio multilínea no constante en coeficientes enteros ['xyz', '+byz'], y devuelve otra cadena como salida 'byz+xyz' donde la misma expresión se ha ordenado de la siguiente manera:

  • Todos los monomios aparecen en orden creciente de número de variables, por ejemplo: "xyz-xz" -> "-xz+xyz"

  • Si dos monomios tienen el mismo número de variables, aparecen en orden lexicográfico, por ejemplo: "xzy+zby" -> "byz+xyz"

Para separar las letras de los números y símbolos he usado re.split(r'[0-9+-]', "3a+2ac-abc") -> ['', 'a', '', 'ac', 'abc'].
He podido procesar estos valores, pero tengo problemas al ordenarlos de forma lexicográfica cuando las cadenas tienen la misma longitud.
También he intentado usar sorted(..., key=lambda x: (-len(x), x)) o sorted(..., key=len), lo cual ordena el arreglo de forma opuesta.

He logrado definir de manera correcta los valores en la lista, ¿como podría ordenarlos?

2
  • ¿Podemos asumir que el grado de cada variable es 1?
    – Jorge Luis
    el 13 may. a las 7:34
  • ninguna variable debe poseer algún exponente mayor a 1 para este caso
    – user327285
    el 13 may. a las 7:52

1 respuesta 1

2

Partamos de una cadena que representa un polinomio. Usemos una expresión regular para extraer cada uno de sus monomios:

monomios = re.finditer(r"(^|[+-])([0-9]*)([a-z]+)", polinomio)
monomios = [monomio.groups() for monomio in monomios]

En esta expresión regular hay dos cosas imporantes. En el grupo de los coeficientes usamos * lo cual significa que puede no haber ningún dígito. Lo hacemos así porque si algún monomio tiene coeficiente 1 o -1, es habitual que se escriba +x o -x: sin el número.

La otra cosa importante es que el grupo que busca coincidir con el signo + o - empieza con ^. Eso significa inicio de cadena. Lo ponemos porque es habitual que si el primer monomio tiene coeficiente positivo, no se escriba explícitamente. Necesitamos que todos los monomios tengan su signo. Así que aquellos monomios que no tengan signo, les añadimos un +.

monomios = [(signo or '+', coeficiente, variables)
            for signo, coeficiente, variables in monomios]

A continuación ordenamos alfabéticamente las variables de cada monomio:

monomios = [(signo, coeficiente, ''.join(sorted(variables)))
            for signo, coeficiente, variables in monomios]

Por último ordenamos los monomios. Tenemos un doble criterio: primero por cantidad de variables; es decir, por longitud de variables. Y después lexicográficamente. Como la función sort recibe un argumento key, que es el criterio de orden, escribamos estos dos criterios en una función de comparación.

def compare(str1: tuple[str, str, str], str2: tuple[str, str, str]):
    # Tomo las variables
    vars1 = str1[2]
    vars2 = str2[2]

    # Comparo por longitud
    if len(vars1) < len(vars2):
        return -1
    if len(vars1) > len(vars2):
        return 1

    # Comparo lexicográficamente
    if vars1 < vars2:
        return -1
    if vars1 > vars2:
        return 1
    
    # Caso de igualdad
    return 0

Para que esta función la pueda recibir la función sort hay que convertirla usando functools.cmp_to_key.

monomios.sort(key=cmp_to_key(compare))

En este punto tenemos una lista de tuplas. Convertimos las tuplas a string y la lista de strings a string:

monomios = [''.join(monomio) for monomio in monomios]
monomios = ''.join(monomios)

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.