我将如何获得相邻交换的最小数量，以均衡包含相同数字但顺序不同的两个列表（PYTHON）

Question

我想知道如何获得最小数目的相邻交换，以均衡包含相同数字但顺序不同的两个列表。例如...

array_1 = [4,3,2,1]
array_2 = [1,2,3,4]

我们希望找到最少数量的相邻交换，以将array_1转换为array_2。

答案将是6 ADJACENT掉期

[如果有人可以在python中为此创建函数，将不胜感激。谢谢。

Answer 1

我假设数字都是不同的

两步：

1）使array_2排序

2）解决何时对array_2进行排序

我将使用此测试用例：

array_1 = [1, 7, 3, 2, 6]
array_2 = [3, 2, 6, 7, 1]

第一步：

我们要做的是进行替换，以便对array_2进行排序。最明显的方法是遍历array_2的每个元素（3、2、6、7、1）。您将第一个替换为'1'，第二个替换为'2'，依此类推。]

示例：

   array_2 = [3, 2, 6, 7, 1]
-> array_2 = [1, 2, 3, 4, 5]
因此您已替换了3-> 1、2-> 2、6-> 3、7-> 4、1-> 5。现在使用相同的替换，更新array_1。

   array_1 = [1, 7, 3, 2, 6]
-> array_1 = [5, 4, 1, 2, 3]
所以现在等效于将[5, 4, 1, 2, 3]交换为[1, 2, 3, 4, 5]。

2）解决此问题>

这是众所周知的，答案是数组中反转对的数量。例如，在[5、4、1、2、3]中，存在4 + 3 = 7个反演，因此需要7次交换。例如，请参考this。

我将提供第一部分的代码

array_1 = [1, 7, 3, 2, 6]
array_2 = [3, 2, 6, 7, 1]
replace_scheme = {} # dictionary
for i in range(len(array_2)): # zero-index still work
    replace_scheme[array_2[i]] = i # array_2[i] -> i
for i in range(len(array_1)):
    array_1[i] = replace_scheme[array_1[i]] # Replaces
print (array_1, inversions(array_1)) # We don't need to update array_2, we know it's sorted