Bienvenue sur IndexError.

Ici vous pouvez poser des questions sur Python et le Framework Django.

Consultez la FAQ pour améliorer vos chances d'avoir des réponses à vos questions.

Ordonner une liste à partir d'une autre liste

+4 votes

Je cherche à ordonner une liste à partir d'une autre. Ex: la liste qui donne l'ordre est ['I2', 'I1', 'I3'], la liste à trier est ['I1', 'I2', 'I3'], je veux avoir à la fin ['I2', 'I1', 'I3'].

Pour le moment j'ai fait ca :

    list_sorted = []
    for el in list_order:
        if el in list_to_sort:
             list_sorted.append(el)

Ca marche nickel quand j'ai pas de répétition dans la liste à trier mais j'aimerais l'étendre aux listes avec répétition et j'aimerais ne pas faire un while avec un compteur à incrémenter.

Y a un moyen de faire ca en python de façon élégante ?

[EDIT] j'ai vu pas mal de set dans les réponses pour l'extension aux listes avec répétitions. En fait quand je disais étendre, je pensais plus à si on donne ['I1', 'I2', 'I3', 'I2'] ca renvoie ['I2', 'I2', 'I1', 'I3']. Ce que je veux c'est un genre de sort ou je peux lui donnér un ordre et pas que ca utilise le lexicographique habituel.

demandé 4-Sep-2015 par Morkav (208 points)
edité 5-Sep-2015 par Morkav

6 Réponses

+8 votes
 
Meilleure réponse

Voici une solution permettant un tri stable, conservant l'entièreté des données de la liste à trier :

def priority_sort(to_sort, order):
    """Return a sorted to_sort, with elements sorted as in order iterable"""
    priority = {e:p for p, e in enumerate(order)}
    return sorted(to_sort, key=lambda e: priority[e])

# usage example
to_sort = [4, 1, 1, 2, 3, 3, 4, 2]
order   = [4, 2, 1, 3]

print(priority_sort(to_sort, order))  # [4, 4, 2, 2, 1, 1, 3, 3]

Un autre intérêt de cette approche est qu'il est possible de conserver le dictionnaire de priorité pour d'éventuels tris futurs. Gain de temps possible sur beaucoup de données.

Autre amélioration : une priorité par défaut pour les éléments non renseignés dans order :

from collections import defaultdict

def priority_sort(to_sort, order, default_priority=-1):
    priorities = defaultdict(lambda: default_priority,
                             {e:p for p, e in enumerate(order)}
                            )
    return sorted(to_sort, key=lambda e: priorities[e])

to_sort = [1, 2, 3, 4, 5]
order   = [4, 2, 1, 3]

print(priority_sort(to_sort, order))  # [5, 4, 2, 1, 3]
print(priority_sort(to_sort, order, default_priority=len(order)))  # [4, 2, 1, 3, 5]
répondu 4-Sep-2015 par lucas (2,340 points)
edité 8-Sep-2015 par lucas

+1

Si je lis mieux la question, je pense que c'est bien le comportement attendu : retrouver les répétions dans la liste triée.

La combinaison sorted() + dict assure une performance bien meilleure pour les grandes listes, et ça c'est bien :)

Exactement ce que je cherchais ! Super !

+2 votes

Si tu veux enlever les doublons de ta liste à trier, utilise le type set de python :

list_sorted = []
for el in list_order:
    if el in set(list_to_sort):
         list_sorted.append(el)
répondu 4-Sep-2015 par bubulle (2,256 points)

J'aime bcp les set aussi mais quand je disais que je voulais pouvoir étendre aux listes avec répétition, je pensais plutôt à si on donne ['I1', 'I2', 'I3', 'I2'] ca renvoie ['I2', 'I2', 'I1', 'I3'].

En effet, je n'ai compris ta question qu'après.

+1 vote

Si tu veux être "élégant" tu peux utiliser une liste en intention (j'intègre le set de bubulle, je connaissais pas d'ailleurs, merci):

list_sorted = [el for el in list_order if el in set(list_to_sort)]

mais si ton code marche déjà et est compréhensible, c'est juste pour faire joli :)

Je pense qu'il y a aussi une solution avec sorted et une lambda function, mais je passe la main sur ce coup-là.

répondu 4-Sep-2015 par furankun (1,434 points)

mais si ton code marche déjà et est compréhensible, c'est juste pour
faire joli :)

J'suis d'accord, si le code est simple et lisible, le but est atteint, il est inutile de pondre un pavé incompréhensible (sauf par toi et quelques éclairés) juste pour faire "beau", en effet la beauté du code réside dans sa clarté et sa simplicité, et pas juste montrer "qu'on connaît des trucs en python qu'on est les seuls à connaître" en contre-partie d'un code illisible et incompréhensible.

Yep je suis entièrement d'accord. Le code que j'ai écrit pour faire le cas simple me va, le côté élégant c'était pour le cas avec répétition (cf EDIT)

+3 votes
list_order = [2, 1, 10, 3, 4]
list_to_sort = [4, 4, 3, 2, 6, 1, 3]
[i for i in list_order if i in list_to_sort] 

=> [2, 1, 3, 4]

répondu 4-Sep-2015 par Bastos (124 points)

j'aime bien mais en fait ca supprime des éléments (le 4 devrait être présent deux fois..)

0 votes

Création d'un compteur ordonné voir https://docs.python.org/3/library/collections.html

from collections import Counter, OrderedDict

class OrderedCounter(Counter, OrderedDict):
"""compteur qui enregistre les éléments dans l'ordre de la première rencontre"""

    def __repr__(self):
        return '%s(%r)' % (self.__class__.__name__, OrderedDict(self))

    def __reduce__(self):
        return self.__class__, (OrderedDict(self),)

list_order = ['I2', 'I1', 'I3', 'dans_l_ordre_mais_pas_a_trier']
list_to_sort = [ 'a_trier_mais_pas_dans_l_ordre_initial', 'I1', 'I2', 'I3', 'I2', 'I3', 'I3']

# initialisation des compteurs à 0 dans l'ordre de list_order
od = OrderedDict.fromkeys(list_order, 0)
oc = OrderedCounter(od)

# mise à jour des compteurs basée sur liste_to_sort
oc.update(list_to_sort)

sorted_list = list(oc.elements())

Traitements possibles:

print(oc)
print('sorted_list:', sorted_list)
print('top 3:', oc.most_common(3)) # classement en fonction du nb d'occurences
print('I2:', oc['I2'])  # accès au compteur de I2
print('dans_l_ordre_mais_pas_a_trier:', oc['dans_l_ordre_mais_pas_a_trier'])

print('\nTraitement de la liste via un iterateur:')
for e in oc.elements():
    print(e)

Résultats:

OrderedCounter(OrderedDict([('I2', 2), ('I1', 1), ('I3', 3), ('dans_l_ordre_mais_pas_a_trier', 0), ('a_trier_mais_pas_dans_l_ordre_initial', 1)]))
sorted_list: ['I2', 'I2', 'I1', 'I3', 'I3', 'I3', 'a_trier_mais_pas_dans_l_ordre_initial']
top 3: [('I3', 3), ('I2', 2), ('I1', 1)]
I2: 2
dans_l_ordre_mais_pas_a_trier: 0

Traitement de la liste via un iterateur:
I2
I2
I1
I3
I3
I3
a_trier_mais_pas_dans_l_ordre_initial
répondu 11-Sep-2015 par glickind (196 points)
+4 votes

Il suffit d'utiliser le paramètre key de la méthode sort (tri sur place) ou de la builtin sorted (renvoie d'une nouvelle liste).
Rappel: En utilisant le paramètre key, le trie se fait sur ce que renvoie la fonction associée. Il suffit donc de renvoyer les indices de la liste référence:

lst = [1, 2, 4, 4, 3, 1, 1, 4, 3, 2]
print(lst)
ref = [4, 2, 3, 1]

lst.sort(key=ref.index)
print(lst)
répondu 12-Nov-2015 par Olygrim (128 points)

Très joli en effet.

Juste une remarque néanmoins :
Le solution de lucas (qui utilise aussi key) sera plus performante car list.index() doit re-parcourir la liste de référence à chaque étape du tri.
Ca ne sera pas un problème pour des petites listes, mais il vaut mieux l'avoir en tête.

Quand tu dis qu'il faudra re-parcourir la liste à chaque étape, veux-tu dire que si c'est l'indice 500 (par exemple), alors il faut d'abord passer par les 500 précédents?

Ça me surprend. Je pensais que l'indice permettait d'avoir directement accès à l'objet.

ref[500] accède directement à l'objet pointé, pas de problème là-dessus.

Par contre, à supposer que ref[500] == 'toto', faire ref.index('toto') va effectivement parcourir les 500 premières cases de ref et les comparer à 'toto' avant de trouver que 'toto' est bien à la case 500.

Ah oui, tu as raison. Effectivement il faudra comparer chaque valeur à chaque fois. L'utilisation d'un dictionnaire est une bonne idée donc :)

...