Алгоритм подсчета версий с функцией слияния - PullRequest
Новая
       22

Алгоритм подсчета версий с функцией слияния

0 голосов
/ 17 мая 2018

Я пытаюсь закодировать оптимальную версию алгоритма подсчета версий. У меня ошибка в строке 84: объект int не повторяется.

Но я не могу понять, почему у меня эта проблема.

Функция mergesort: объединение списка номеров в порядке возрастания (этот работает, когда я использую его один)

Функция merge_and_count: взять два объединенных массива на входе и посчитать количество элементов из левого массива, которые больше, чем элементы правого массива

Функция sort_and_count: функция, которая выдаст количество инверсий (она также возвращает список, потому что позволяет использовать рекурсивность)

Вот код: 

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)):
        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

    else:
        size = len(L)
        size2 = len(L) // 2

        for i in range(0, size2):
            A.append(L[i])
        for i in range(size2,size-1):
            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)

1 Ответ

0 голосов
/ 17 мая 2018

Вы забыли вернуть пару из sort_and_count здесь: 

def sort_and_count(L):

    i = 0
    A = []
    B = []

    if len(L) == 1:
        return 0  # <-- You forgot to return the list as second element
    ...
    ...

Так как эти строки 

    (rA,A) = sort_and_count(A)
    (rB,B) = sort_and_count(B)

ожидают итерацию в правой части оператора присваивания и получают толькоцелое число, вы получаете int объект не повторяется ошибка.

...