Home > Enterprise >  Inversion Counting Algorithm implementation in Python,cannot unpack non-iterable int object
Inversion Counting Algorithm implementation in Python,cannot unpack non-iterable int object

Time:08-02

This is my implementation of the inversion counting algorithm using a divide and conquer approach, the problem i am having is it keeps saying there is a type error, cannot unpack non-iterable int object, in line 45, and line 10

  • A is the unsorted list
  • B is the sorted left half of the array
  • C is the sorted right half of the array
  • D is the merged and sorted array
  • X, Y are the number of inversion in the left/right half of the array respectively
  • Z the the inversion that is scattered between B and C, so across the middle
# count the number of inversions 
def SortandCount(A:list):
    length = len(A)
    mid = length//2
    firsthalf = A[ : mid]
    secondhalf = A[mid :]
    if length == 1:
        return 0
    else: 
        B, X = SortandCount(firsthalf)
        C, Y = SortandCount(secondhalf)
        D, Z = CountSplitInv(B, C)
    
    return D, X   Y   Z


def CountSplitInv(B,C):
    # takes 2 sorted list B C merging it into sorted list D 
    # as well as counting the inversions
    # B = [1,4] C[2,3,5]
    invnum = 0
    D = []
    i = j = 0

    length = len(B)
    while i < length and j <len(C):
        if (B[i] <= C[j] ):
           D.append(i)
           i  =1
        if(B[i] > C[j]):
            D.append(C[j])
            j =1
            invnum  = len(B) - i
    if(i != length):
        D.extend(B[i:])
    if(j != len(C)):
        D.extend(C[j:])
    return D,invnum

def inversions_countin_wrapper(lst: list) -> int:
    return SortandCount(lst)[1]


A=[14,2,3]
num=SortandCount(A)
print(num)

the error is

Traceback (most recent call last):
  File "/Users/Algorithms/divide&conquer/inversion.py", line 45, in <module>
    num=SortandCount(A)
  File "/Users/Algorithms/divide&conquer/inversion.py", line 10, in SortandCount
    B, X = SortandCount(firsthalf)
TypeError: cannot unpack non-iterable int object

Appreciate any kind of help!!! Please !!! Been stuck on this for 3 days (stupid ,i know) >_8<

this is the high level pesudo code i used

CodePudding user response:

B, X = SortandCount(firsthalf)

Requires SortandCount to return two values. If the function executes to the end, it will do so. But what if it terminates early?:

    if length == 1:
        return 0

Then it only returns a 0. So there's no value for X. Which is what the error message is telling you.

  • Related