Complexity to insert subset of array to minimize order inversions
I'm not entirely sure what to call this, or if there are good reductions to other known problems, so references to those will help.
As input you're given an array A of length n of distinct elements, and another array B of length k < n that contains a subset of the elements in the first array, potentially in a new order. The output should be an array of length n with every element in A such that the relative order of every element in B is preserved, and the order of elements in $A \setminus B$ should minimize the number of inversions with respect to A.
For example, take as input A := [1, 2, 3, 4], B := [1, 4, 2], then the output could be either [1, 3, 4, 2] or [1, 4, 2, 3] as each have one inversion caused by the placement of the 3, which is the smallest you can achieve without altering the order in B.
This can pretty trivially be done in $O(k (n - k) + n)$, where for each element in $A \setminus B$ you scan through $B$ and compute the number of inversions that would happen if inserting there, and simply put the element in the gap that minimizes it. However, this is worst case $O(n^2)$ depending on k, and that seems avoidable. 864
In particular, it seems like there should be some invariants in the relative order of elements that need to be placed that should save some time.
There are small tweaks that make it better, but that don't improve the worst case complexity. For example, take two elements $c1, c2 \in A \setminus B$ where c1 comes before c2 in A. After finding c1's optimal position, c2 must come after it in the final order.
Psuedo Code
``` fn min_inversions(a_order, b_order) # all ordered elements for constant time access b_set := set(b_order) # all elements left of element considering for rank inversions left_set := set() # where to start looking for insertions # equal to the last insertion found, helps time, but not worst case start_index := 0 # index to start scan for minimum # array for each gap between elements in b_order, we insert the missing elements here # since we process missing elements in order, we can append to preserve order insertions := [[] for _ in 0..len(b_order) + 1]
for ai in a_array:
if ai in b_set:
# don't need to locate, but mark as left of considered element to compute inversions
left_set += set(ai)
else:
# number of inversions for placement in any considered gap
# initial value is arbitrary as we only care about relative value, but this setting is "correct"
inversions = [size(lef_set)]
for bi in slice(b_order, start_index):
change = -1 if bi in left_set else 1
inversions += [inversions[-1] + change]
start_index = start_index + argmin(inversions)
insertions[start_index] += [ai]
# here insertions has everything from A\B in the optimal gap, just need to interleave with the initial B
result := interleave(insertions, b_order)
``` 864