CODEWITHSUNDEEP
pythonmergesortinversion
Jane. S
Jane. S

Reputation: 11

Counting inversion in python: int object not iterable error

Hi I am new to python and I am having trouble on the counting inversion problem using mergesort. The error said ""int" object is not iterable. However, I don't think I am iterating any number at this stage. Since I am stucked here, I am not sure if there are more bugs in this code.. Can anyone help me figuring out what is going on here? Thank you very much. 

import sys

def merge_and_count_inversions(x, y):
    sorted_array = [] 
    count = 0 
    i, j = 0, 0
    #print ("inside merge", x, y)
    while i < len(x) and j < len(y):
        if x[i] > y[j]:
            count += len(x) - i
            sorted_array.append(y[j])
            j += 1
        else:
            sorted_array.append(x[i])
            i += 1
    while i < len(x):
        sorted_array.append(x[i])
        i += 1
    while j < len(y):
        sorted_array.append(y[j])
        j += 1
    #print ("overall count = ", count )
    #print ("sorted_array", sorted_array)
    return count, sorted_array

def get_number_of_inversions(a, b, left, right):
    number_of_inversions = 0
    if right - left <= 1:
        return number_of_inversions
    ave = (left + right) // 2
    number_of_inversions_A, a[left:ave] = get_number_of_inversions(a, b, left, ave)
    #print ("left list", a[left : ave])
    #print ("number_of_inversions left half = ", number_of_inversions )
    number_of_inversions_B, a[ave:right] = get_number_of_inversions(a, b, ave, right)
    #print ("right list", a[ave : right])
    #print ("number_of_inversions left + right half = ", number_of_inversions )
    number_of_inversions_C, sorted_list = merge_and_count_inversions(a[left:ave],a[ave:right])
    tot_inversions = number_of_inversions_A + number_of_inversions_B + number_of_inversions_C 
    #print ("number_of_inversions overall = ", number_of_inversions )
    return tot_inversions, sorted_list

input_ = input()
n, *a = list(map(int, input_.split())) #n is the length of a
b = n * [0]
get_number_of_inversions(a, b, 0, len(a))
print(get_number_of_inversions(a, b, 0, len(a)))

And the error said:

<ipython-input-60-e1f94361f38a> in get_number_of_inversions(a, b, left, right)
     33     ave = (left + right) // 2
     34     print ("average = ", ave)
---> 35     number_of_inversions_A, a[left:ave] =   get_number_of_inversions(a, b, left, ave)
     36     print ("left list", a[left : ave])
     37     print ("number_of_inversions left half = ", number_of_inversions )

<ipython-input-60-e1f94361f38a> in get_number_of_inversions(a, b, left, right)
     33     ave = (left + right) // 2
     34     print ("average = ", ave)
---> 35     number_of_inversions_A, a[left:ave] =    get_number_of_inversions(a, b, left, ave)
     36     print ("left list", a[left : ave])
     37     print ("number_of_inversions left half = ", number_of_inversions )

TypeError: 'int' object is not iterable

Upvotes: 0

Views: 250

Answers (1)

EvensF
EvensF

Reputation: 1610

Well, I'm not versed in the Merge Sort algorithm but in get_number_of_inversions() you have two exits:

First:

number_of_inversions = 0
if right - left <= 1:
    return number_of_inversions

And:

return tot_inversions, sorted_list

You use the return values in an expression like:

number_of_inversions_A, a[left:ave] = get_number_of_inversions(a, b, left, ave)

So sometimes you return an integer and sometimes a tuple. My guess is that when you return an integer, you get this error.

Upvotes: 1

Related Questions