序列调整 cost

评估从 arr 调整到 GT_arr 需要的步数；本质上为：排序问题

• 将 GT_arr 中的 元素对应下标 idx 作为 arr 中元素排序时比较的 key
• 完成升序排列需要的总步数 即为 cost
• 排序算法可用任意的，下以选择排序为例

# 将 arr 调整到 GT_arr 使用 选择排序 需要的步数 cnt
def select_sort(arr, target_arr):
    cnt = 0
    n = len(arr)

    key = {val: idx for idx, val in enumerate(target_arr)}

    for i in range(n - 1):
        for j in range(i + 1, n):
            # 实际 rank 值
            if key[arr[j]] < key[arr[i]]:  # swap
                arr[i], arr[j] = arr[j], arr[i]
                cnt += 1
    return cnt

举例

import numpy as np

GT_array = np.arange(1, 5)
print(GT_array)

# 随机生成两个无序的 arr
a = np.random.permutation(GT_array)
b = np.random.permutation(GT_array)

print(a)
print(b)

# 计算 序列调整 cost
print(select_sort(a, GT_array))
print(select_sort(b, GT_array))

[1 2 3 4]  # GT_arr
[2 4 1 3]  # a
[1 2 4 3]  # b
3
1