逆序数的讨论

今天初中班主任问我一道题：

想了想这就是逆序数的问题。逆序数为，一个从1到n的排列的逆序数个数。对于这道题，就是一个从1到8的逆序数为8的排列的个数。

相关论文：https://kns.cnki.net/kcms2/article/abstract?v=3uoqIhG8C44YLTlOAiTRKgchrJ08w1e7_IFawAif0mzHoqs1uKxDSYgJRaQREx5nVao7p1E2WoiyrIiHvmygVojJKmfvGnmx&uniplatform=NZKPT&src=copy

大概思路就是递归:

def w(n, j):
    s = 0
    if j < 0 or j > n * (n - 1) // 2:
        return 0
    if n == 1:
        return 1
    for k in range(j - n + 1, j + 1):
        s += w(n - 1, k)
    return s

print(w(8, 8))

oeis：https://oeis.org/A008302

然后引申为一道leetcode题，求排列的逆序数。

https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solutions/216984/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/

可以用归并排序做，每次排序的过程中利用子数组的有序性即可求出逆序个数。

如图所示，逐层排序的过程中将还未排序的数的个数相加即为答案。

复习一下归并排序。总之是分治的方法。