I am wondering how I would get the minimum number of adjacent swaps to equalize two lists that contain the same numbers but in different orders. For example...
array_1 = [4,3,2,1]
array_2 = [1,2,3,4]
We would want to find the smallest number of adjacent swaps to turn array_1 into array_2.
The answer would be 6 ADJACENT swaps
If anyone can make a function for this in python it would be appreciated. Thank you.
I assumed the numbers are all distinct
Two steps:
1) Make array_2 sorted
2) Solve for when array_2 is sorted
I'll be using this test case:
array_1 = [1, 7, 3, 2, 6]
array_2 = [3, 2, 6, 7, 1]
First step:
What we're going to do is do a substitution, such that array_2 is sorted. The most obvious way is to go through each element of array_2 (3, 2, 6, 7, 1). You replace the first one with '1', the second one with '2' and so on.
Example:
array_2 = [3, 2, 6, 7, 1]
-> array_2 = [1, 2, 3, 4, 5]
So you've replaced 3->1, 2->2, 6->3, 7->4, 1->5. Now using the same substitution, update array_1.
array_1 = [1, 7, 3, 2, 6]
-> array_1 = [5, 4, 1, 2, 3]
So now it's equivalent to swapping [5, 4, 1, 2, 3] to [1, 2, 3, 4, 5].
2) Solving this
This is well known, and the answer is the number of inversion pairs in the array. For example in [5, 4, 1, 2, 3] there are 4+3=7 inversions, so 7 swapps are required. Refer to this for example.
I'll provide the first part's code
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
