J'essaye de reproduire l'algorithme qui calcule le nombre d'inversions d'une liste (la merge version "optimale")
Exemple: pour la liste [2, 4, 1, 3, 5],il y a trois inversions (2, 1), (4, 1), (4, 3).
Le problème, c'est tout simplement que le résultat est faux pour le moment.
Je ne rentre pas trop dans les détails mais je pense que ceux qui connaissent cet algorithme comprendront l'idée de mon code:
def mergesort(list):
"""Fonction qui classe les nombres de la liste par ordre croissant.
Celle la fonctionne bien et renvoie une liste"""
taille = len(list)
liste_1_temp = []
liste_2_temp = []
if len(list) > 1:
for i in range(0,(taille//2)):
liste_1_temp.append(list[i])
for i in range((taille//2),taille):
liste_2_temp.append(list[i])
mergesort(liste_1_temp)
mergesort(liste_2_temp)
i = 0
j = 0
k = 0
while i < len(liste_1_temp) and j < len(liste_2_temp):
if liste_1_temp[i] < liste_2_temp[j]:
list[k] = liste_1_temp[i]
i+=1
k+=1
else:
list[k] = liste_2_temp[j]
j += 1
k+=1
while (i < len(liste_1_temp)):
list[k] = liste_1_temp[i]
i+=1
k+=1
while (j < len(liste_2_temp)):
list[k] = liste_2_temp[j]
j+=1
k+=1
liste_finale = list
return liste_finale
def merge_and_count(A,B):
"""Fonction qui doit renvoyer """
i = 0
j = 0
count = 0
C = []
while (i < len(A) and (j < len(B))):
if A[i] > B[j]:
C.append(B[j])
count += (len(A)-i)
i = 0
j += 1
else:
C.append(A[i])
i += 1
return count,C
def sort_and_count(L):
i = 0
A = []
B = []
if len(L) == 1:
return (0,L)
else:
size = len(L)
size2 = len(L) // 2
for i in range(0, size2):
A.append(L[i])
for i in range(size2,size):
B.append(L[i])
(rA,A) = sort_and_count(A)
(rB,B) = sort_and_count(B)
(r,L) = merge_and_count(mergesort(A),mergesort(B))
return ((rA+rB+r),L)
Les inversions se détectent ligne 28 de ton code. Je complète :
def mergesort(list):
"""Fonction qui classe les nombres de la liste par ordre croissant.
Celle la fonctionne bien et renvoie une liste"""
taille = len(list)
liste_1_temp = []
liste_2_temp = []
if len(list) > 1:
for i in range(0,(taille//2)):
liste_1_temp.append(list[i])
for i in range((taille//2),taille):
liste_2_temp.append(list[i])
mergesort(liste_1_temp)
mergesort(liste_2_temp)
i = 0
j = 0
k = 0
while i < len(liste_1_temp) and j < len(liste_2_temp):
if liste_1_temp[i] <= liste_2_temp[j]:
list[k] = liste_1_temp[i]
i+=1
k+=1
else:
for kk in range(i, len(liste_1_temp)):
print(liste_1_temp[kk] , liste_2_temp[j])
list[k] = liste_2_temp[j]
j += 1
k+=1
while (i < len(liste_1_temp)):
list[k] = liste_1_temp[i]
i+=1
k+=1
while (j < len(liste_2_temp)):
list[k] = liste_2_temp[j]
j+=1
k+=1
liste_finale = list
return liste_finale
from random import randrange
def inversions(L):
print("===== Les inversions ok=====")
n=len(L)
for i in range(n):
for j in range(i+1,n):
if L[i]>L[j]:
print(L[i],L[j])
L=[randrange(15) for i in range(randrange(2,12))]
print(L)
inversions(L)
print("===== Les inversions merge =====")
mergesort(L)
Je me suis pas énormément penché sur ton problème mais j'ai trouvé quelqu'un qui résolvait cela. Je te conseille d'essayer de retrouver chaque partie de ton code dans le sien pour espérer trouver ton problème !
Bonne chance
OpenClassrooms retire tellement d'aiguilles de nos pieds qu'on pourrait ne plus trouver le foin de notre botte :)
Merci pour ta réponse. J'ai effectivement vu celui là, et j'arrive justement pas à trouver une différence (bien sur quelques trucs superficiels mais qui reviennent au même).
Je pense qu'il me manque quasiment rien pour que ça fonctionne, un petit détail que je ne trouve pas!
Visiblement soit j'ai mal compris ta question soit tu as mal compris ma réponse
Tu cherches bien à lister les inversions d'une liste d'entiers ? Bon, ta fonction mergesort(list) y parvient, il suffit juste de rajouter la ligne que je t'ai indiquée. Voici une version basée sur ton code et qui produit la liste des inversions (liste inversions dans le code ci-dessous) :
inversions=[]
def mergesort(list):
"""Fonction qui classe les nombres de la liste par ordre croissant.
Celle la fonctionne bien et renvoie une liste"""
taille = len(list)
liste_1_temp = []
liste_2_temp = []
if len(list) > 1:
for i in range(0,(taille//2)):
liste_1_temp.append(list[i])
for i in range((taille//2),taille):
liste_2_temp.append(list[i])
mergesort(liste_1_temp)
mergesort(liste_2_temp)
i = 0
j = 0
k = 0
while i < len(liste_1_temp) and j < len(liste_2_temp):
if liste_1_temp[i] <= liste_2_temp[j]:
list[k] = liste_1_temp[i]
i+=1
k+=1
else:
# Juste rajouter cette ligne
inversions.extend((liste_1_temp[kk] , liste_2_temp[j]) for kk in range(i, len(liste_1_temp)))
list[k] = liste_2_temp[j]
j += 1
k+=1
while (i < len(liste_1_temp)):
list[k] = liste_1_temp[i]
i+=1
k+=1
while (j < len(liste_2_temp)):
list[k] = liste_2_temp[j]
j+=1
k+=1
liste_finale = list
return liste_finale
L=[12, 11, 4, 3, 5, 4, 10, 14]
print(L)
mergesort(L)
print(inversions)
Ok je pense que c'est moi qui avait mal compris ta solution !!
J'ai pas fais exactement comme toi, mais du coup ça marche aussi maintenant !! C'est vrai que la tienne est plus courte et tiens sur une fonction !!
Pour ma part j'avais bétement oublier de compléter la liste C dans merge_and_count , j'ai donc rajouté deux boucles while pour compléter. Merci d'avoir pris le temps de comprendre mon code
def approxsup(n):
return (n - n//2)
def mergesort(list):
"""Fonction qui classe les nombres de la liste par ordre croissant.
Celle la fonctionne bien et renvoie une liste"""
taille = len(list)
liste_1_temp = []
liste_2_temp = []
if len(list) > 1:
for i in range(0, (taille // 2)):
liste_1_temp.append(list[i])
for i in range((taille // 2), taille):
liste_2_temp.append(list[i])
mergesort(liste_1_temp)
mergesort(liste_2_temp)
i = 0
j = 0
k = 0
while i < len(liste_1_temp) and j < len(liste_2_temp):
if liste_1_temp[i] < liste_2_temp[j]:
list[k] = liste_1_temp[i]
i += 1
k += 1
else:
list[k] = liste_2_temp[j]
j += 1
k += 1
while (i < len(liste_1_temp)):
list[k] = liste_1_temp[i]
i += 1
k += 1
while (j < len(liste_2_temp)):
list[k] = liste_2_temp[j]
j += 1
k += 1
liste_finale = list
return liste_finale
def merge_and_count(A, B):
"""Fonction qui doit renvoyer """
i = 0
j = 0
count = 0
C = []
while (i < len(A) and (j < len(B))):
if A[i] > B[j]:
print([B[j]])
C.append(B[j])
count += (len(A) - i)
j += 1
else:
C.append(A[i])
i += 1
while (i < len(A)):
C.append(A[i])
i += 1
while (j < len(B)):
C.append(B[j])
j += 1
return count, C
def sort_and_count(L):
i = 0
A = []
B = []
if len(L) == 1:
return (0, L)
else:
size = len(L)
size_2 = approxsup(size)
for i in range(0, size_2):
A.append(L[i])
for i in range(size_2, size):
B.append(L[i])
(rA, A) = sort_and_count(A)
(rB, B) = sort_and_count(B)
(r, L) = merge_and_count(mergesort(A), mergesort(B))
return ((rA + rB + r), L)
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères