5

Eu tenho uma lista de tuplas e eu quero ordenar elas, o porém é que são dois critérios diferentes.

Cada tupla tem a seguinte configuração: (peso, beneficio)

A ordenação que eu quero fazer é da seguinte forma:

Do elemento com maior benefício para o com menor benefício. Caso duas tuplas tenham o mesmo valor de benefício o critério de desempate é o peso. A tupla com o menor peso ganha.

Portanto, dada a lista de tuplas:

[(4,2),(5,2),(7,3),(9,4),(6,4)]

A lista ordenada será:

[(6,4),(9,4),(7,3),(4,2),(5,2)]

Para utilizar dois elementos como critério de ordenação eu encontrei esta solução. Mas tentando usar retorna os dois campos com o mesmo critério.

listaqq = [(4,2),(5,2),(7,3),(9,4),(6,4)]
sortedLista = sorted(listaqq, key=operator.itemgetter(1,0), reverse=True)

[(9, 4), (6, 4), (7, 3), (5, 2), (4, 2)]

Dando uma outra procurada aqui encontrei esta possível solução, mas não consegui entender para aplicar da forma que preciso.

Teria alguma forma de fazer isso usando sorted?
Talvez usando lambda, mas como seria a expressão?

3 Respostas 3

3

O problema de usar itemgetter ou tuplas (como sugerido em outra resposta) é que ambos os elementos serão ordenados pelo mesmo critério (ou ambos em ordem crescente, ou ambos em ordem descrescente). Mesmo se você usar reverse=True, isso será aplicado em ambos.

Se a ideia é que um seja em ordem decrescente e outro em ordem crescente, uma alternativa é inverter o sinal de um deles:

def comp(item): # primeiro item em ordem decrescente, segundo em ordem crescente
   return -item[1], item[0]

listaqq = [(4,2),(5,2),(7,3),(9,4),(6,4)]

sortedLista = sorted(listaqq, key=comp)
print(sortedLista) # [(6, 4), (9, 4), (7, 3), (4, 2), (5, 2)]

Ou, usando lambda em vez de uma função:

sortedLista = sorted(listaqq, key=lambda item: (-item[1], item[0]))

Nesse caso não precisa usar reverse=True. Como eu inverti o sinal do segundo elemento da tupla, eles serão ordenados em ordem decrescente. No caso de empate, será usado o valor do primeiro elemento (em ordem crescente).

O resultado será a lista [(6,4),(9,4),(7,3),(4,2),(5,2)].


Já usando a outra solução que você viu:

def compare(t1, t2):
    # compara o segundo elemento de cada tupla, em ordem decrescente
    cmp = t2[1] - t1[1]
    if cmp == 0: # se forem iguais, compara o primeiro elemento de cada tupla, em ordem crescente
        cmp = t1[0] - t2[0]
    return cmp

import functools

sortedLista = sorted(listaqq, key = functools.cmp_to_key(compare))
print(sortedLista)

A ideia é que a função de comparação retorne um número negativo se o primeiro elemento é "menor" (ou seja, se deve vir antes na ordenação), 0 se forem iguais e um número positivo se for "maior" (se deve vir depois na ordenação).

Então eu posso simplesmente subtrair o segundo elemento da segunda tupla pelo segundo elemento da primeira: se o resultado for positivo, quer dizer que a primeira tupla deve vir depois na ordenação (ou seja, os elementos são ordenados em ordem decrescente).

Se o resultado da subtração é zero, quer dizer que o segundo elemento das tuplas são iguais, e aí eu faço o desempate pelo primeiro elemento (mas agora subtraindo o elemento da primeira tupla antes, para que seja em ordem crescente).

Por fim, eu uso cmp_to_key para que a função de comparação seja convertida para uma key function e possa ser usada em sorted.

3

Para resolver esta questão podes utilizar o seguinte código:

listaqq = [(4, 2), (5, 2), (7, 3), (9, 4), (6, 4)]
print(sorted(listaqq, key=lambda c: (-c[1], c[0])))

Observe que neste código a função lambda está ordenando listaqq em função do segundo valor da tupla e, em caso de empate, o desempate se dará pelo primeiro valor da respectiva tupla.

Agora se você deseja trabalhar com quaisquer listas de tuplas, com valores inteiros, podes utilizar o seguinte código:

n = int(input('Quantos tuplas? '))
listaqq = list()
for d in range(1, n + 1):
    listaqq.append(tuple(map(int, input(f'Digite a {d}º tupla: ').split())))
print(sorted(listaqq, key=lambda c: (-c[1], c[0])))

Quando executamos este segundo código devemos digitar a quantidade de tuplas que queremos montar. Em seguida devemos digitar todos o valores de cada tupla, na mesma linha, separados por um só espaço e pressionar enter.

Posteriormente o código irá realizar a ordenação das tuplas em função do último índice de cada tupla.

1
  • 1
    Faltou fazer o desempate quando c[1] é igual, o seu código resulta em [(9, 4), (6, 4), (7, 3), (4, 2), (5, 2)] mas o resultado deve ser [(6, 4), (9, 4), (7, 3), (4, 2), (5, 2)] - deixei uma resposta com uma alternativa para o desempate
    – hkotsubo
    Commented 23/10/2020 às 10:53
3

O parâmetro "key" aceita qualquer função, que vai receber um elemento da sequência que vai ser ordenada, e deve retornar um elemento que possa ser comparado direto com ">" e "<" pelo Python.

O padrão de usar o "itemgetter" é para aproveitar essa função que já existe, de forma que o código fique mais elegante - mas eu, pessoalmente, acho que complica a legibilidade. (o itemgetter também pode ter um pequeno ganho de performance - mas teria que ser um trecho de código muito específico para isso realmente dar diferença - por exemplo, se for uma ordenação em milhões de resultados.)

Em suma, é só você criar sua própria função de chave. Como o Python consegue comparar tuplas, comparando o primeiro item, e se der empate, comparando o segundo item. No seu caso específico, é só inverter a tupla - devolver uma tupla em que o benefício seja comparado antes do peso:

def comp(item):
   return item[1], item[0]

sortedLista = sorted(listaqq, key=comp, reverse=True)

Como as funções desse tipo são em geral simples, é comum se escrever a função de compararação como uma uma função "lambda" - funciona exatamente como uma função, mas pode conter uma única expressão, e não precisa do comando "return":


sortedLista = sorted(listaqq, key=lambda item: (item[1], item[0]), reverse=True)
3
  • Acho que isso não produz o resultado esperado, pois no caso vai ordenar por item[1] em ordem decrescente, e o desempate com item[0] também será em ordem decrescente (mas o desempate deve ser em ordem crescente) - deixei uma resposta com uma alternativa (mas não sei se foi gambiarra demais ou se tem um jeito mais elegante - fique à vontade para comentar lá)
    – hkotsubo
    Commented 23/10/2020 às 10:52
  • ah - na verdade é só fazer lambda item; -item[1], item[0] e tirar o reverse.
    – jsbueno
    Commented 23/10/2020 às 13:50
  • 1
    isso - como voce fez lá - eu mesmo usei sesse pattern nos últimos tempos - nem lembro onde.
    – jsbueno
    Commented 23/10/2020 às 13:51

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .