(TypeError:无法解压缩不可迭代的int对象)用于使用合并排序的倒置计数器

Question

我正在尝试进行一个递归调用，以对抗一个数字列表的倒排数。

例如：[3,1,2,4]，两个反转版本是(3,1)和(3,2)。

因此，算法应该返回2。

我使用merge_sort方法尝试了这一点。

def merge(x,y,last_inversion_sum):
    x_length = len(x)
    y_length = len(y)
    n = x_length+y_length
    i=j=0
    inversion = 0
    merged_list = []
    while i<x_length and j <y_length:
        if x[i]>y[j]:
            merged_list.append(y[j])
            j+=1
        else:
            merged_list.append(x[i])
            i+=1
            inversion+=1

    if i == x_length:
        merged_list.extend(y[j:])
    else:

        merged_list.extend(x[i:])

    inversion = inversion+last_inversion_sum
    return merged_list,inversion


def compute_inversion(a):
    array_length = len(a)
    if array_length<=1: return 0

    L,inversion1 = compute_inversion(a[:int(array_length / 2)])
    R,inversion2 = compute_inversion(a[int(array_length / 2):])
    inversion_sum = inversion1+inversion2

    return merge(L,R,inversion_sum)

lizt = [3,2,1,5]

_,inversion_num = compute_inversion(lizt)
print(inversion_num)

弹出错误：

Traceback (most recent call last):
  File "D:/A.LXR/inversion.py", line 40, in <module>
    _,inversion_num = compute_inversion(lizt)
  File "D:/A.LXR/inversion.py", line 32, in compute_inversion
    L,inversion1 = compute_inversion(a[:int(array_length / 2)])
  File "D:/A.LXR/inversion.py", line 32, in compute_inversion
    L,inversion1 = compute_inversion(a[:int(array_length / 2)])
TypeError: cannot unpack non-iterable int object

Process finished with exit code 1

哪里出问题了？有人能帮我吗？

Answer 1

您的compute_inversion(a)函数应该始终返回相同类型的值，一个列表和一个int，即使在array_length<=1：

你可以这样做：

def compute_inversion(a):
    array_length = len(a)
    if array_length<=1: return a, 0

    L,inversion1 = compute_inversion(a[:int(array_length / 2)])
    R,inversion2 = compute_inversion(a[int(array_length / 2):])
    inversion_sum = inversion1+inversion2

    return merge(L,R,inversion_sum)

它现在起作用了，其结果是：

3