Partage

Algorithme Counting Inversion

17 mai 2018 à 9:58:54

Salut! 

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)

Merci pour votre aide :)

-
Edité par Nol38 17 mai 2018 à 11:26:35

Vous êtes demandeur d'emploi ?
Sans diplôme post-bac ?

Devenez Développeur web junior

Je postule
Formation
en ligne
Financée
à 100%
17 mai 2018 à 10:59:06

Et du coup c'est quoi le problème ?
OpenClassrooms retire tellement d'aiguilles de nos pieds qu'on pourrait ne plus trouver le foin de notre botte :)
17 mai 2018 à 11:26:03

Pardon !! J'ai oublié de le préciser. Mon code ne renvoie pas le bon résultat tout simplement..
17 mai 2018 à 18:29:21

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)

ce qui affiche

[8, 5, 12, 8, 6, 4, 9]                                                                                                 
===== Les inversions ok=====                                                                                           
8 5                                                                                                                    
8 6                                                                                                                    
8 4                                                                                                                    
5 4                                                                                                                    
12 8                                                                                                                   
12 6                                                                                                                   
12 4                                                                                                                   
12 9                                                                                                                   
8 6                                                                                                                    
8 4                                                                                                                    
6 4                                                                                                                    
===== Les inversions merge =====                                                                                       
8 5                                                                                                                    
8 6
6 4
8 4
5 4
8 4
12 4
8 6
12 6
12 8
12 9




-
Edité par PascalOrtiz 17 mai 2018 à 18:33:11

18 mai 2018 à 8:54:15

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 :)
18 mai 2018 à 16:25:12

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!

18 mai 2018 à 18:12:19

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)
[12, 11, 4, 3, 5, 4, 10, 14]
[(12, 11), (4, 3), (11, 3), (12, 3), (11, 4), (12, 4), (5, 4), (11, 4), (12, 4), (11, 5), (12, 5), (11, 10), (12, 10)]




18 mai 2018 à 18:21:46

Salut ! 

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)



Algorithme Counting Inversion

× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
  • Editeur
  • Markdown