Discussion :

[chrislomb]

Bonjour à tous, je poste ce message car je cherche une façon alternative de trier une liste de n-uplet dans l'ordre lexicographique.
Pour commencer j'ai établis un programme simple qui tri chaque élément de la liste dans l'ordre lexicographique (sans prendre en compte que les éléments sont des listes eux mêmes). Cette fonction marche mais je souhaiterais en écrire une prenant en paramètre la longueur de chaque n-uplet, donc en comparant chaque éléments d'un n-uplet aux même élément des autres n-uplets.
Ainsi par exemple, pour liste=[[1,0,3],[0,2,3],[0,2,2]]
on regarde liste[i][0] pour mettre en premier dans la liste le n-uplet dont le premier élément est le plus petit, en cas d'égalité on regarde alors l'élément suivant liste[i][1].
Ici la liste une fois triée donnerait alors : [[0,2,2],[0,2,3],[1,0,3]]
J'ai tenté avec des boucles mais je ne parviens à rien.. cela ne fonctionne pas.
Toute aide serait vraiment la bienvenue..
Merci d'avance

[wiztricks]

Salut,

J'ai tenté avec des boucles mais je ne parviens à rien.. cela ne fonctionne pas.
Toute aide serait vraiment la bienvenue..

Le programmeur Python utilise "sorted" (ou la méthode "list.sort"):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
>>> liste=[[1,0,3],[0,2,3],[0,2,2]]
>>> sorted(liste)
[[0, 2, 2], [0, 2, 3], [1, 0, 3]]
>>>

après le débutant doit peut être réaliser cela "à la main" en écrivant ses boucles et ses tests car c'est formateur.
Si vous êtes dans ce cas, postez le code que vous avez essayé de faire et expliquez ce qui bloque...

- W

[chrislomb]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def tri(liste):  #méthode de tri par insertion
    n=len(liste)
    #liste=liste.copy()
    for i in range(n):
        position=i
        while position>0 and liste[position]<liste[position-1]:
            liste[position-1],liste[position]=liste[position],liste[position-1]
            position=position-1
        return(liste)

Voici mon premier code qui fonctionne mais il n'est pas défini en fonction du nombre d'éléments dans mon n-uplets, j'ai donc essayé de reprendre un modèle similaire mais en le conditionnant sur les éléments dans les n-uplets pour déplacer ceci mais cela ne fonctionne pas et j'ai beau essayer de changer et de le faire tourner " à la main" je ne comprends pas pourquoi:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def tri3(n_u,liste): #n_u est le nombre d'éléments dans le n_uplet
    n=len(liste)
    for i in range(0,n):
        position1=i
        pos1=liste[position1-1]
        print(i,liste,position1)
        while position1>0 and liste[position1][0]<liste[position1-1][0]: #si le premir élément d'un n-uplet est inférieur à celui d'un n-uplet précédent alors on les échange
            liste[position1],liste[position1-1]=liste[position1-1],liste[position1]
        for j in range(1,n_u): #on réitère l'opération pour chaque élément
            position2=j
            pos2=liste[position1][position2]
            print(j,liste[position1][position2])
            while position1>0 and position2<n_u and pos2<liste[position1-1][position2]:
                liste[position1-1],liste[position1]=liste[position1],liste[position1-1]
                position1=position1-1
                position2=position2-n_u-1
            liste[position1]=pos1
    return(liste)

Merci beaucoup pour votre réponse

[wiztricks]

Salut,

Pour trier, il faut un algo. et dans le premier code çà ressemble à ce qu'on appelle tri à bulle. A la base, çà repose sur la capacité à comparer les 2 objets de la liste à trier.
Si vous ne savez pas que Python sait comparer 2 listes par ordre lexicographique, il vous suffit d'écrire votre propre fonction. A défaut, vous ne faites plus vraiment du "tri à bulle" et on ne sait trop ce que vous êtes parti à coder...

- W

[chrislomb]

Salut,

Pour trier, il faut un algo. et dans le premier code çà ressemble à ce qu'on appelle tri à bulle. A la base, çà repose sur la capacité à comparer les 2 objets de la liste à trier.
Si vous ne savez pas que Python sait comparer 2 listes par ordre lexicographique, il vous suffit d'écrire votre propre fonction. A défaut, vous ne faites plus vraiment du "tri à bulle" et on ne sait trop ce que vous êtes parti à coder...

- W

Ecrire ma propre fonction oui, mais je ne vois pas de ou partir car j'ai essayé maintes tentatives vaut-il mieux utiliser des boucles for i et for j pour comparer chaque indice ?
La deuxième fonction j'ai essayé d'après les conseils de quelqu'un qui m'a orienté vers le même format mais je vois bien que cela ne fonctionne pas, cela parait pourtant vraiment simple mais ça fait deux semaines que je suis dessus et je ne vois pas vraiment;

[potozuzu]

Pour commencer j'ai établis un programme simple

Salut !

Je t'invite à regarder de plus près comment fonctionne le tri par insertion (https://fr.wikipedia.org/wiki/Tri_par_insertion), c'est le nom de l'algorithme de tri que tu as "établi". Je trouve d'ailleurs que les algorithmes de tri ne sont pas vraiment simples à comprendre...

Je ne comprends pas le but de tri3, puisque tri permet déjà de trier des listes de n-uplets (car python sait évaluer [0, 2, 2] < [0, 2, 3]).

Quelques pistes, si tu veux quand même ré-écrire tri3 :
-> La ligne position1=position1-1 de tri est CAPITALE, il ne faut pas l'enlever dans tri3 (dans la boucle while de la boucle for i), sinon tu ne ramènes pas vraiment la "collection d'éléments déjà triée" vers le début.
-> La boucle for j est sensée boucler sur les mêmes éléments que la boucle for i, et tu veux sortir de la boucle for i pour écrire for j. Cette boucle veut évaluer les 2e éléments de chaque sous-liste (liste[j][1]). Puis on recommence avec le 3e (liste[k][2]), etc.
-> Je crois que tu as essayé de factoriser ces différentes boucles for ; en ce cas ça devrait ressembler à un truc de ce genre

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for i in range(n):
    for j in range(n_u):

[tyrtamos]

Bonjour,

Il est difficile de programmer une fonction de tri plus efficace que celle de Python, mais quand on veut quand même en programmer une, le tri par insertion est une bonne solution: il est déjà assez efficace (plus que le tri bulle!), et assez simple à comprendre..

Voilà une solution en Python:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def triInsertion(L):
    """Trie sur place par insertion la liste L
    """
    for i in range(1, len(L)):
        if L[i] < L[i-1]:
            for k in range(0, i):
                if L[i] < L[k]:
                    X = L.pop(i)
                    L.insert(k, X)
                    break

On voit bien les 2 méthodes utilisées pour modifier la liste: X=L.pop(i) extrait la valeur d'indice i et la met dans X, et L.insert(k, X) insère la valeur X dans L à l'indice k

Exemple d'application pour trier les éléments de L qui sont ici des sous-listes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
L = [['Xavier', 0.2589], ['Alain', 0.84569], ['Martine', 1.26587], ['Julien', 4.5893], ['Christiane', 1.02458], ['Yves', 8.0125], ['Albert', -1.8]]
triInsertion(L)
print(L)
[['Alain', 0.84569], ['Albert', -1.8], ['Christiane', 1.02458], ['Julien', 4.5893], ['Martine', 1.26587], ['Xavier', 0.2589], ['Yves', 8.0125]]

A noter qu'on peut trier des cas plus complexes en ajoutant un argument supplémentaire 'key' comme avec sort de Python:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def triInsertionK(L, key=None):
    """Trie sur place par insertion la liste L avec possibilité de
       préciser avec key les éléments à comparer
    """
    if key==None:
        key = lambda v: v
    for i in range(1, len(L)):
        if key(L[i]) < key(L[i-1]):
            for k in range(0, i):
                if key(L[i]) < key(L[k]):
                    X = L.pop(i)
                    L.insert(k, X)
                    break

On peut, par exemple trier la liste précédente selon le 2ème élément (indice=1) de chaque sous-liste:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
triInsertionK(L, key=lambda v: v[1])
print(L)
[['Albert', -1.8], ['Xavier', 0.2589], ['Alain', 0.84569], ['Christiane', 1.02458], ['Martine', 1.26587], ['Julien', 4.5893], ['Yves', 8.0125]]

Et si les sous-listes étaient composées de plus de 2 éléments, mais qu'on voulait les trier selon les 2 premiers, on pourrait faire cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

triInsertionK(L, key=lambda v: v[:2])

A noter qu'on peut augmenter l'efficacité du tri par insertion pour les grandes listes en notant que à chaque boucle i, les éléments de 0 à i sont déjà ordonnés: on peut donc faire une recherche par dichotomie au lieu de chercher en testant toutes les valeurs. Mais ça complique un peu...

[chrislomb]

Merci beaucoup pour toutes vos réponses, mais j'ai pour consigne de garder en paramètre dans ma fonction le nombre d'éléments dans mes n-uplets. Ainsi mon algorithme doit trier ma liste en fonction de cela c'est purquoi mon premier jet utilisant le tri à bulles ou un tri par insertion ne répond pas à la question.. Je trouve cela certe, un peu stupide, ayant remarqué que Python, trie seul les n-uplets, mais je dois me plier à la consigne c'est pourquoi j'ai du mal à adapter l'une de ces méthodes
Grâce à vous je comprends déjà mieux les différentes façons de trier

[chrislomb]

J'ai écrit cette nouvelle fonction qui trie ma liste de n-uplet par rapport au premier élément de chaque n-uplet et qui l'inverse lorsque la liste commence par des 1: (sachant que le premier élément est soit 0 soit 1, que le deuxième est soit 0 soit 1 soit 2 et le troisème sur le même modèle etc).
Cela marche, il faudrait que je l'adapte à tous les éléments mais à partir du deuxième élément je n'y parviens pas..

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
def insertion(liste,taille):
    for i in range(0,taille,1):
        tmp=liste[i][0]
        tmp1=liste[i]
        j=i
        while j>0 and liste[j-1][0]<tmp:
            liste[j]=liste[j-1]
            j=j-1
        liste[j]=tmp1
    if liste[0][0]==1:
        liste.reverse()
    return(liste)

exemple de réponse :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
In [72]: (executing lines 1 to 134 of "ordre lexicographique 3.py")
Quelle est le nombre de n-uplets désirés?5
Quel est le nombre d'éléments désirés dans le n-uplet?3
La liste d'origine est : [[0, 0, 1], [1, 2, 1], [0, 1, 1], [0, 2, 2], [1, 2, 2]]
La liste une fois triée dans l'ordre lexicographique est : [[0, 2, 2], [0, 1, 1], [0, 0, 1], [1, 2, 2], [1, 2, 1]]

[wiztricks]

Ecrire ma propre fonction oui, mais je ne vois pas de ou partir car j'ai essayé maintes tentatives vaut-il mieux utiliser des boucles for i et for j pour comparer chaque indice ?

Une fonction qui compare les triplets a et b commence par l'instruction def compare(a, b): et comme vous avez la chance d'avoir len(a) == len(b), il suffit d'une boucle qui compare a[i] à b[i] et qui retourne le résultat dès que a[i] != b[i].

- W

[chrislomb]

Merci beaucoup, je vais essayer cela tout de suite!!

J'ai encore une petite question (j'aimerais vraiment améliorer mon niveau en programmation python), quel est la différence entre un paramètre key et un autre?
Que fait key exactement dans un cas plus général? c'est une partie que l'on a pas vu en cours et j'aimerais bien comprendre à quoi cela sert exactement pour pouvoir éventuellement le réutiliser plus tard.
Mercii

[tyrtamos]

Que fait key exactement dans un cas plus général? c'est une partie que l'on a pas vu en cours et j'aimerais bien comprendre à quoi cela sert exactement pour pouvoir éventuellement le réutiliser plus tard.

Dans le 1er code que j'ai donné avec key, il s'agit de modifier les éléments à prendre dans les comparaisons du tri.

Par exemple, si on prend: key=lambda v: v[1], les comparaisons de mon tri par insertion seront modifiées comme suit:

if L[i] < L[i-1]: deviendra en fait: if L[i][1] < L[i-1][1]
if L[i] < L[k]: deviendra en fait: if L[i][1] < L[k][1]:

C'est à dire que le tri de la liste sera fait en fonction du 2ème élément (indice=1) des sous-listes et pas des sous-listes complètes.

C'est ce qui est utilisé aussi dans la méthode sort et dans la fonction sorted de Python.

Ayant compris cela, on peut modifier cette fonction de tri par insertion en changeant simplement les 2 comparaisons ci-dessus!

[chrislomb]

Merci!!!