algorithmperformanceoptimization# Minimum number of inversions to make one array identical to another

### Algorithm

### Implementation

I'm trying to create an efficient algorithm to solve a problem that provides 2 arrays, and asks what's the minimum number of inversions in array B to make it identical to identical to array A (inversions = only adjacent elements can be swapped). Both arrays are guaranteed to contain the same elements. Examples:

a) A = ['a', 'b', 'c', 'd', 'e'] and B = ['b', 'e', 'd', 'c', 'a']. The minimum number of inversions would be 7 by doing the following inversions on array B: (e d), (e c), (e a), (d c), (d a), (c a) and (b a).

b) A = ['a', 'e', 'c', 'd', 'b'] and B = ['a', 'c', 'e', 'b', 'd'] would need 2 inversions, because: (c e) and (b d)

Tried it with the most basic algorithm I could think of, findind the index of element A[i] within B and placing it in the correct place but that's O(n^2). It becomes inefficient with larger inputs and ends up not solving the problem.

I was wondering what could be a better algorithm for this

Solution

First, observe that we can count the number of adjacent swaps needed to sort the array by counting inversions: Pairs of indices (i, j) that are the wrong way around: i < j but a[j] > a[i].

Why is this equivalent to your problem? Let's take two elements b, a that are in the wrong order:

..., b, a, ...

now a swap will change this to

..., a, b, ...

That is, this "removes" a single inversion. You can choose your swaps such that each swaps removes an inversion. So the number of swaps of adjacent elements needed is indeed equal to the number of inversions.

You can count inversions in quadratic time using a naive algorithm, but that is of course too slow.

A better approach is to solve this using a variation of Merge Sort in O(n log n) time:

In addition to the sorted subarray, return an integer indicating the number of inversions in the subarray. Sum these counts for the recursive calls of mergesort with the inversions counted during merging:

- When two elements from left and right are equal or the left element is smaller than the right one, everything is fine.
- If however the right element is greater than the left one, we have an inversion of the right element with all the remaining elements in the left subarray.

Now, with your current problem statement, there's a tiny twist: You have a "target" array, so the "order" your elements have to be in is not the "normal" order (say, ascending for integers), but rather the order set out in your "target" list. Luckily this is easy to deal with: Just redefine our comparison function! Simply build an index (f.e. hash table) from element to index in the array, and compare indices!

Here's a Lua implementation of this, in case you get stuck with implementing any details, but I recommend you to try to work out the details yourself; it's a good exercise.

(One thing to be careful with when reading the code: Unlike many other programming languages, indices in Lua start at 0; you do not need to pre-allocate arrays.)

If you don't know Lua, just treat this as pseudocode. It should be quite readable given Lua's friendly syntax :)

```
-- Merges two sorted lists; elements of `left` come before those of `right`
local function merge(left, right, less_than)
local result = {}
local inversions = 0
local i, j, k = 1, 1, 1
while i <= #left and j <= #right do
-- Compare "head" element, insert "winner"
if less_than(right[j], left[i]) then
-- Right list came first, this is an inversion with all the larger elements left in the left list
inversions = inversions + (#left - i + 1)
result[k] = right[j]
j = j + 1
else
result[k] = left[i]
i = i + 1
end
k = k + 1
end
-- Add remaining elements of either list or other_list
for offset = 0, #left - i do
result[k + offset] = left[i + offset]
end
for offset = 0, #right - j do
result[k + offset] = right[j + offset]
end
return result, inversions
end
-- Splits a list into two halves of roughly equal size
local function split(list)
local left, right = {}, {}
local mid = math.floor(#list / 2)
for i = 1, mid do
left[i] = list[i]
end
for i = mid + 1, #list do
table.insert(right, list[i])
end
return left, right
end
-- Sorts a list, returning a sorted list and the number of inversions
local function mergesort(list, less_than)
if #list <= 1 then
return list, 0 -- already sorted
end
local left, right = split(list)
-- Sort left half & count inversions in left half
local left_sorted, left_inversions = mergesort(left, less_than)
-- Sort right half & count inversions in right half
local right_sorted, right_inversions = mergesort(right, less_than)
-- Merge halves, count inversions *between* left & right half
local sorted, left_right_inversions = merge(left_sorted, right_sorted, less_than)
return sorted, left_inversions + right_inversions + left_right_inversions
end
local function count_inversions(from_list, to_list)
-- Build index from element to index in target list
local idx = {}
for i, v in ipairs(to_list) do
idx[v] = i
end
-- Compare according to wanted indices in target list
local function less_than(a, b)
return idx[a] < idx[b]
end
local _, inversions = mergesort(from_list, less_than)
return inversions
end
print(count_inversions({'a', 'b', 'c', 'd', 'e'}, {'b', 'e', 'd', 'c', 'a'})) -- 7
print(count_inversions({'a', 'e', 'c', 'd', 'b'}, {'a', 'c', 'e', 'b', 'd'})) -- 2
```

- Worst case in Max-Heapify - How do you get 2n/3?
- How to check whether a matrix is a framed matrix?
- Identify connected subnetworks, constrained by edge attributes
- Is there a way to generate a random variate from a non-standard distribution without computing CDF?
- Most efficient way to calculate VWAP(VOLUME WEIGHTED AVERAGE PRICE) for trading algorithm
- How to find and replace all occurrences of a substring in a string?
- How to find kth smallest element in a BST when the tree may be modified frequently?
- Calculate distance between two latitude-longitude points? (Haversine formula)
- How does one make a Zip bomb?
- How to calculate the midpoints of each triangle edges of an icosahedron
- Calculate circular shift pairs in a list
- Uniformly randomly generate a vector of k unsigned ints that sums to N
- Bin packing with fixed number of bins of varying capacities and item-to-bin compatibility constraints
- Mapping elementwise Tuple Using Template Function
- Find the longest prefix for a table of tokenized strings
- Count Unguarded Cells in the Grid (recursion)
- Kalman Filter Prediction Implementation
- My ALV Tree balance factors calculate incorrectly
- Infix to postfix left one parentheses at the end when expression is fully enclosed
- C++ quick sort algorithm
- Merge Sort Function not working when size of vector is not 2^n
- Given an array a of n integers, and q queries, for each value from index l to index r, add x to the value
- Count mountain arrays
- Get the number of all possible combinations that give a certain product
- getting TLE in leetcode question 212- word search 2 using backtrcaking even after pruning, how do i optimize it more
- Maximizing the sum of Adjacent sum in an array
- Weighted random selection from array
- If f(n) = O(g(n)), is log(f(n)) = O(log(g(n))?
- Why is KNN slow with custom metric?
- Based on a condition, how to remove an item from the processed array and move it to another array?