TypeError: '<' non pris en charge entre les instances de 'tuple' et 'str'

J'ai une méthode qui construisent un arbre de huffman qui est comme suit:

def buildTree(tuples) :
    while len(tuples) > 1 :
        leastTwo = tuple(tuples[0:2])                  # get the 2 to combine
        theRest  = tuples[2:]                          # all the others
        combFreq = leastTwo[0][0] + leastTwo[1][0]     #enter code here the branch points freq
        tuples   = theRest + [(combFreq,leastTwo)]     # add branch point to the end
        tuples.sort()                                  # sort it into place
    return tuples[0]            # Return the single tree inside the list

mais alors que je me nourris de la fonction avec le paramètre suivant:

[(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')]

Je reçois le message d'erreur que

  File "<stdin>", line 7, in buildTree
    tuples.sort()
TypeError: '<' not supported between instances of 'tuple' and 'str'

Pendant le débogage, j'ai trouvé l'erreur était dans tuples.sort().

leastTwo est un tuple de tuples, qui vous puis les envelopper dans l'autre tuple avec combFreq (un entier). Vous ne pouvez pas comparer que intérieur tuple avec les chaînes dans le deuxième élément de chacun des autres tuples.
En d'autres termes, vous ne pouvez ajouter (int, str) tuples, pas (int, ((int, str), (int, str))) des n-uplets.
Maintenant, si vous souhaitez uniquement pour trier sur la premier valeur de chaque tuple, vous devez spécifier une clé de tri que des extraits.
Non pas que je voudrais utiliser le tri ici; utilisation d'une file d'attente de priorité à la place (voir Comment mettre en œuvre des Files d'attente de Priorité en Python?).

OriginalL'auteur rhazkoomar | 2017-01-28

  1. 6

    L'erreur est levée parce que vous êtes la création de noeuds contenus dans (priority, (node, node)) forme. Pour l'égalité des priorités, Python essaie de comparer un symbole à partir d'un nœud feuille (de sorte que le deuxième élément dans un (priority, symbol) nœud n-uplet) avec le (node, node) tuple à partir d'un noyau de nœud:

    >>> inner = (combFreq, leastTwo)
>>> inner
(2, ((1, 'b'), (1, 'd')))
>>> theRest[1]
(2, 'c')
>>> theRest[1] < inner
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'str' and 'tuple'

    Pour la construction d'un arbre de huffman, si vous souhaitez trier votre tableau de nœuds, vous ne vraiment besoin de trier sur la priorité, en ignorant le reste de la n-uplets (symboles ou des nœuds enfants):

    tuples.sort(key=lambda t: t[0])

    Avec cette correction, votre buildTree() fonction produit un arbre:

    >>> buildTree([(1, 'b'), (1, 'd'), (1, 'g'), (2, 'c'), (2, 'f'), (3, 'a'), (5, 'e')])
(15, ((6, ((3, 'a'), (3, ((1, 'g'), (2, 'c'))))), (9, ((4, ((2, 'f'), (2, ((1, 'b'), (1, 'd'))))), (5, 'e')))))

    Personnellement, je préfère utiliser une file d'attente de priorité au lieu de cela, en évitant de tri à chaque fois. Voir Comment mettre en œuvre des Files d'attente de Priorité en Python?

    Merci beaucoup Martijn Pieters .Les gens comme vous que le monde beau.

    OriginalL'auteur Martijn Pieters