評估從 arr 調(diào)整到 GT_arr 需要的步數(shù)；本質(zhì)上為：排序問題
- 將
GT_arr中的 元素對應(yīng)下標(biāo)idx作為arr中元素排序時比較的 key - 完成升序排列需要的總步數(shù) 即為 cost
- 排序算法可用任意的，下以選擇排序為例
# 將 arr 調(diào)整到 GT_arr 使用 選擇排序 需要的步數(shù) 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)
# 隨機(jī)生成兩個無序的 arr
a = np.random.permutation(GT_array)
b = np.random.permutation(GT_array)
print(a)
print(b)
# 計算 序列調(diào)整 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
