算法反转次数 (Python)

Question

我正在尝试完成加州大学圣地亚哥分校在 Coursera 上提供的算法工具箱的代码分配。该作业要求您使用合并排序算法的变体计算数字序列中的反转次数。为了更好地描述问题：

https://i.stack.imgur.com/CCBU8.jpg

我使用了合并排序算法的变体，但得到的答案不正确，老实说我卡住了。

值得注意的是，在解释我尝试的内容之前，这段代码涉及递归，我承认我发现它很难理解。

除了通常的调试之外，我还尝试将我的代码与已知解决方案进行比较，看看我可能哪里出错了。我可以提交这些作为我的解决方案，但就我而言，这将是一种欺骗，我想知道我的代码哪里出了问题（老实说，这让我发疯）。

#Uses python3
import sys

def merge_sort(A):
    if len(A) <= 1:
        return A, 0    
    else:
        middle = (len(A)//2)
        left, count_left = merge_sort(A[:middle])
        right, count_right = merge_sort(A[middle:])
        result, count_result = merge(left,right)
        return result, (count_left + count_right + count_result)

def merge(a,b):
    result = []
    count = 0
    while len(a) > 0 and len(b) > 0:
        if a[0] < b[0]:
            result.append(a[0])
            a.remove(a[0])
        else:
            #count = count + (len(a) - 1)
            result.append(b[0])
            b.remove(b[0])
            count += (len(a) - 1) #this is the important line
    if len(a) == 0:
        result = result + b
    else:
        result = result + a
    return result, count 

if __name__ == '__main__':
    input = sys.stdin.read()
    n, *a = list(map(int, input.split()))
    c = n * [0]
    array, inversion = merge_sort(a)
    print(array)
    print(inversion)

下面列出了我在测试中使用的两个示例输入：

# ex 1:
3
3 1 2

请注意，第一个数字是序列中值的数量（评分者需要）。反转的预期答案是 2。我的代码得到 0。

# ex 2:
6
3 1 9 3 2 1

反转的预期答案是 9。我得到 4。

Answer 1

两次更正：

if a[0] <= b[0]:（请注意，许多互联网示例和课程忽略了 or equal 大小写，破坏了算法的内在稳定性，这种情况对于正确的 inv. 计数也很重要）

和 count += len(a) - 我们需要考虑 a 中的所有项目与当前 b 项目

形成倒置

def merge(a,b):
    result = []
    count = 0
    while len(a) > 0 and len(b) > 0:
        if a[0] <= b[0]:   
            result.append(a[0])
            a.remove(a[0])
        else:
            result.append(b[0])
            b.remove(b[0])
            count += len(a)
    if len(a) == 0:
        result = result + b
    else:
        result = result + a
    return result, count

算法反转次数 (Python)

Algorithm Number of Inversions (Python)

python

algorithm

recursion

mergesort

inversion