Tri avancé dans une liste imbriquée

Version imprimable

Bonjour, je suis nouveau et j'aurais besoin d'aide sur une fin de projet, j'ai actuellement une fonction qui me trie une liste suivant l'age inverse des personnes grace a la fonction sorted depuis une liste imbriquée (1 liste dans l'autre), toutefois je voudrais le faire sans utiliser des fonctions de type sort ou sorted.

C'est a dire qu'en clair je voudrais le faire a la main, sans que "sort" n'apparaisse :)

La partie concernée est celle-ci :
Code:

1 2 3 4 5 6 from datetime import datetime liste = [['WILSON', 'MIKE', 'H', '26/06/1950'], ['EMERIC', 'JAMES', 'H', '27/06/1960'], ['MOPAL', 'ARTHUR', 'H', '27/06/1966']] def agepersonne(): print(sorted(liste, key=lambda item: datetime.strptime(item[3], '%d/%m/%Y'), reverse=True)) agepersonne()
Au final le résultat est celui-ci :
Code:

1 2 3 4 5 [['MOPAL', 'ARTHUR', 'H', '27/06/1966'], ['EMERIC', 'JAMES', 'H', '27/06/1960'], ['WILSON', 'MIKE', 'H', '26/06/1950']]
Ce qui est tout a fait correct par rapport a ce que je souhaite, sauf que je n'arrive pas a le faire " a la main... " .

11/01/2018, 09h13
wiztricks

Salut,

Citation:

Envoyé par Whisper40

Ce qui est tout a fait correct par rapport a ce que je souhaite, sauf que je n'arrive pas a le faire " a la main... " .

Vous trouverez sans trop de difficultés un algorithme de tri avec un peu de recherche sur Internet. Vous aurez peut être des difficultés à la coder en Python mais si vous ne postez pas le code que vous avez essayé de faire, on ne va pas pouvoir vous aider ("sort" nous va très bien).

- W

Bonjour,

Juste un petit coup de pouce.

Une petite fonction de tri "insertion" (Python 3). Ce n'est pas le plus rapide des algo de tri, mais il est déjà pas mal et assez simple à comprendre:
Code:

1 2 3 4 5 6 7 8 def triInsertion(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
Pour adapter cette fonction au problème posé, il faut:
- que la comparaison se fasse avec le 4ème élément (indice=3) de chaque sous-liste (ex: L[i] devient L[i][3])
- que chaque date de type '27/06/1966' soit transformée en '19660627' pour que le tri alphabétique coïncide avec le tri chronologique (ex: date => date[6:11] + date[3:5] + date[0:2])
- tenir compte du fait qu'on cherche ce tri en inverse.

Merci pour ta partie de code, malheureusement je l'avais déja vu et essayé mais bon xD :weird:

Modification, la date est saisie par l'utilisateur de cette manière : "19660627"
J'ai légèrement modifié le code, avec inversion du site < dans le boucle for i.
Par contre je ne vois pas du tout comment m'occuper du trie de la date
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 L = [['WILSON', 'MIKE', 'H', '19500626'], ['EMERIC', 'JAMES', 'H', '19600626'], ['MOPAL', 'ARTHUR', 'H', '19660627']] def triInsertion(L): for i in range(len(L)): if L[i][3] > L[i-1][3]: for k in range(0, i): if L[i] < L[k]: X = L.pop(i) L.insert(k, X) break return L triInsertion(L)

11/01/2018, 18h18
tyrtamos

Non. Tu corriges au pif, et tu n'y arriveras pas comme ça.

Essai de comprendre l'algorithme (fais un dessin sur papier et simule son déroulement) et tu sauras comment le modifier.

Je comprends le principe du programme qui a pour but de placer "une date" en fonction des autres, pour cela il analyse la liste afin de placer "une date" au bon endroit afin de garder la liste triée a chaque ajout.

Entre temps j'ai préféré modifier le code tout en gardant le principe de base.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 L = [['WILSON', 'MIKE', 'H', '19700626'], ['EMERIC', 'JAMES', 'H', '19670626'], ['MOPAL', 'ARTHUR', 'H', '19660627']] def trie(L): for i in range(1, len(L)): temporaire=L[i] j = i - 1 while j >=0 and L[j] > temporaire: L[j+1] = L[j] j -= 1 L[j+1] = temporaire return L print(trie(L))
Le résultat :
Code:

1 2 3 [['EMERIC', 'JAMES', 'H', '19670626'], ['MOPAL', 'ARTHUR', 'H', '19660627'], ['WILSON', 'MIKE', 'H', '19700626']]
Donc il a trié les personnes suivant leur nom dans un ordre alphabétique, j'ai essayé diverses méthodes pour enlever les [[',']] et faire un retour a la ligne après chaque personne mais sans succés..
J'aurais aussi aimé enlever les informations après le prénom, afin d'avoir un résultat du type :
Code:

1 2 3 4 EMERIC JAMES MOPAL ARTHUR WILSON MIKE
Si vous savez comment faire je suis preneur..

Et bien sur j'ai encore une fois essayer de comprendre comment gérer les dates mais je suis désolé ce n'est pas compréhensible pour ma part..
Je n'ai pas d'idée comment m'en sortir avec une variable qui contient YYYYMMJJ..
Merci

12/01/2018, 08h25
wiztricks

Salut,

Citation:

Envoyé par Whisper40

Donc il a trié les personnes suivant leur nom dans un ordre alphabétique, j'ai essayé diverses méthodes pour enlever les [[',']] et faire un retour a la ligne après chaque personne mais sans succés..

Pour trier, il faut comparer et "comparer" est plus simple à comprendre lorsqu'on a une liste d'entiers ou une liste de chaînes de caractères. Avec Python, les séquences d'objets sont aussi comparables i.e. Python sait comparer [ 'EMERIC', 'JAMES', 'H', '19700626'] avec ['EMERIC', 'JAMES', 'H', '19670626'].
note: ayez la curiosité d'essayer de trier ce genre de liste de liste pour voir.

Citation:

Envoyé par Whisper40

Je comprends le principe du programme qui a pour but de placer "une date" en fonction des autres, pour cela il analyse la liste afin de placer "une date" au bon endroit afin de garder la liste triée a chaque ajout.

Pour l'instant, vous n'avez toujours pas compris le principe (savoir comparer) ni comment Python compare lorsque ce sont des séquences.... Et traduire dans votre code que vous ne voulez pas comparer les objets mais le 3ème élément de chaque objet (et c'est déjà ce que disait Tyrtamos dans son premier post).

- W
12/01/2018, 08h55
Whisper40

Excusez moi mais si je n'avais pas compris je n'aurais pas réussi a comparer les noms..
Le code qui est indiqué fonctionne et compare bien les NOMS.
Je ne comprends pas comment comparer un composé de nombre "19890626" , il faut tenir compte de l'année, du mois et du jour..

Bonjour,

Concernant les dates: je t'ai dit que, avec les dates inversées type "19660627", l'ordre chronologique coïncidait avec l'ordre alphabétique.
Cela veut dire que dans les comparaisons entre les dates inversées, on peut dire:
"19500626" < "19600627" est vrai dans la comparaison alphabétique, et cela coïncide avec le fait que "26/06/1950" est une date ANTERIEURE à "27/06/1960"
aussi facilement que "ARTHUR" < "JAMES" est vrai puisque "A" est AVANT "J" dans l'alphabet

A part ça, n’essaie pas de tout faire en même temps. Pense au "discours de la méthode" de Descartes => quand c'est compliqué: on décompose et on avance pas à pas! Donc, on tri d'abord, on inverse ensuite et on retire l'élément en trop 'H' enfin.

Reprends le code initial:
Code:

1 2 3 4 5 6 7 8 def triInsertion(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
Il n'y a que 2 lignes qui font des comparaisons: lignes 3 et 5. Il faut changer ces 2 comparaisons pour adapter l'algorithme à notre problème.

Il ne faut pas changer le sens des comparaisons, sinon, il faut recréer l'algorithme et tu perds du temps inutilement.

Si les dates sont déjà données en version inversées, c'est très simple:

le ligne 3 devient: if L[i][3] < L[i-1][3]:

et la ligne 5 (tu l'avais oubliée dans ta réponse précédente) devient: if L[i][3] < L[k][3]:

C'est aussi simple que ça!

Application:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 def triInsertion3LL(L): for i in range(1, len(L)): if L[i][3] < L[i-1][3]: for k in range(0, i): if L[i][3] < L[k][3]: X = L.pop(i) L.insert(k, X) break liste = [['MOPAL', 'ARTHUR', 'H', '19660627'], ['WILSON', 'MIKE', 'H', '19500626'], ['EMERIC', 'JAMES', 'H', '19600627']] triInsertion3LL(liste) print(liste)
Ce qui affiche:

Code:

[['WILSON', 'MIKE', 'H', '19500626'], ['EMERIC', 'JAMES', 'H', '19600627'], ['MOPAL', 'ARTHUR', 'H', '19660627']]

On a bien les dates dans l'ordre chronologique '19500626' < '19600627' < '19660627'

On veut ensuite des dates dans l'autre sens: il faut inverser la liste:
Code:

1 2 liste.reverse() print(liste)
Ce qui affiche:

Code:

[['MOPAL', 'ARTHUR', 'H', '19660627'], ['EMERIC', 'JAMES', 'H', '19600627'], ['WILSON', 'MIKE', 'H', '19500626']]

On veut suite supprimer le 'H':
Code:

1 2 3 4 for sl in liste: sl.pop(2) print(liste)
Ce qui affiche:

Code:

[['MOPAL', 'ARTHUR', '19660627'], ['EMERIC', 'JAMES', '19600627'], ['WILSON', 'MIKE', '19500626']]

Ce qui est, si j'ai bien compris, le résultat attendu.

Si par contre tu parts d'une date "normale" type '27/06/1966', tu peux créer une petite fonction utilitaire:
Code:

1 2 def invdate(date): return date[6:11] + date[3:5] + date[0:2]
Et dans ce cas, les 2 lignes de comparaison de la fonction de tri doivent être corrigées:
ligne 3 => if invdate(L[i][3]) < invdate(L[i-1][3]):
ligne 5 => if invdate(L[i][3]) < invdate(L[k][3]):

Cela ne changera pas les 2 étapes suivantes (inversion de la liste et élimination du 'H'), et tu trouveras à la fin:

Code:

[['MOPAL', 'ARTHUR', '27/06/1966'], ['EMERIC', 'JAMES', '27/06/1960'], ['WILSON', 'MIKE', '26/06/1950']]

Ok?

Petit complément.
Au début tu ne voulais pas utiliser la méthode .sort() avec l'argument key=lamda... Mais la solution que je t'ai proposée plus haut a un inconvénient: si tu veux trier selon les prénoms, par exemple, tu es obligé de corriger la fonction de tri: c'est dommage!

On peut faire autrement. Voilà comment:
Code:

1 2 3 4 5 6 7 8 9 10 def triInsertion(L, key=None): 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
Avec cette fonction, si on ne donne pas de valeur à key (donc, key==None), on trie en comparant simplement les éléments de la liste (ici les sous-listes). Mais on peut modifier key à l'appel de la fonction, en disant qu'au lieu de comparer un élément 'v', on compare 'v[3]':

Cela donnera avec ton exemple:
Code:

1 2 3 4 5 liste = [['MOPAL', 'ARTHUR', 'H', '19660627'], ['WILSON', 'MIKE', 'H', '19500626'], ['EMERIC', 'JAMES', 'H', '19600627']] triInsertion(liste, key=lambda v: v[3]) print(liste)
Ce qui affichera bien la liste triée selon les dates:

Code:

[['WILSON', 'MIKE', 'H', '19500626'], ['EMERIC', 'JAMES', 'H', '19600627'], ['MOPAL', 'ARTHUR', 'H', '19660627']]

Et si tu as les dates en format normal type '27/06/1960', il faut intégrer, bien sûr, la petite fonction utilitaire d'inversion des dates 'invdate' dans key:

Code:

triInsertion(liste, key=lambda v: invdate(v[3])

J'espère qu'avec tout ça, tu n'as pas seulement résolu ton problème: tu as appris quelque chose que tu pourras reproduire...

12/01/2018, 09h38
wiztricks

Citation:

Envoyé par Whisper40

Excusez moi mais si je n'avais pas compris je n'aurais pas réussi a comparer les noms..
Le code qui est indiqué fonctionne et compare bien les NOMS...

Je vous ai indiqué un test simple pour le montrer.
Si vous n'avez pas la curiosité d'essayer (et de vous poser des questions) comment espérez vous apprendre quoi que ce soit?

- W

Citation:

Envoyé par tyrtamos

J'espère qu'avec tout ça, tu n'as pas seulement résolu ton problème: tu as appris quelque chose que tu pourras reproduire...

Merci beaucoup pour l'ensemble des solutions possibles a ce type de trie, j'ai enfin compris pourquoi la saisie d'une date était décomposée avec

Code:

date[6:11] + date[3:5] + date[0:2]

Je n'avais pas compris que c'était la place des élements..

Je vais m’intéresser ce soir a votre complément afin de le comprendre et le répeter.

Pour le moment je suis partit sur un trie normal :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 L = [['WILSON', 'MIKE', 'H', '26/06/1950'], ['EMERIC', 'JAMES', 'H', '27/06/1960'], ['MOPAL', 'ARTHUR', 'H', '27/06/1966']] def invdate(date): return date[6:11] + date[3:5] + date[0:2] def triInsertion3LL(L): if invdate(L[i][3]) < invdate(L[i-1][3]): if L[i][3] < L[i-1][3]: for k in range(0, i): if invdate(L[i][3]) < invdate(L[k][3]): X = L.pop(i) L.insert(k, X) break def sexe(): for sl in L: sl.pop(2)
Avec pour résultat :
Code:

1 2 3 [['WILSON', 'MIKE', '26/06/1950'], ['EMERIC', 'JAMES', '27/06/1960'], ['MOPAL', 'ARTHUR', '27/06/1966']]
Et j'y ais implanté une nouvelle fonction afin de rendre l'affichage lisible de la manière que je souhaitais avec :
Code:

1 2 3 4 5 6 def affichage(): for i in range(len(L)): for j in range(len(L[i])): print(L[i][j], end=" ") print()
Ce qui a pour résultat :
Code:

1 2 3 4 WILSON MIKE 26/06/1950 EMERIC JAMES 27/06/1960 MOPAL ARTHUR 27/06/1966
Un grand merci pour cette réponse très bien structurée.
Et merci pour ce cours (complément)