toolbox/unstructured_eval/inversion.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-
from typing import List


def inversions(seq: List[int]):
    """
    计算逆序数.
    """
    count = 0
    n = len(seq)
    for i in range(n):
        for j in range(i + 1, n):
            if seq[i] > seq[j]:
                count += 1
    return count


def main():
    seq_list = [
        [0, 1, 2, 3, 4, 5, 6],
        [1, 0, 2, 3, 4, 5, 6],
        [1, 2, 0, 3, 4, 5, 6],
        [3, 4, 5, 6, 0, 1, 2],
    ]
    for seq in seq_list:
        count = inversions(seq)
        print(count)
    return


if __name__ == "__main__":
    main()