3
$\begingroup$

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$ and $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 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. 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 $c_1, c_2 \in A \setminus B$, where $c_1$ comes before $c_2$ in $A$. After finding $c_1$'s optimal position, $c_2$ 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)
```
$\endgroup$
9
  • 1
    $\begingroup$ Interesting question! $\endgroup$ – John L. May 14 at 23:49
  • 1
    $\begingroup$ "This can pretty trivially be done in $O(k (n - k) + n)$." Can you show your code? $\endgroup$ – John L. May 14 at 23:51
  • 1
    $\begingroup$ argmin(inversions)? If there are several indices where the minimum is reached, do your argmin takes the first index? Or select a random one of them? $\endgroup$ – John L. May 16 at 1:13
  • 1
    $\begingroup$ When $A$ and $B$ are disjoint, we consider all inversions. Or what is equivalent, all inversions that involve at least one element of $A$, since the inversions that come purely from elements of $B$ are fixed. $\endgroup$ – John L. May 19 at 4:49
  • 1
    $\begingroup$ So if A = 1, 2 and B = 3, then 1,2,3 is the only merged array with minimum inversions. $\endgroup$ – John L. May 19 at 5:03
1
$\begingroup$

Since this problem is basically about merging the element not in $B$ with element in $B$ to minimize order inversions, this answer will be focused on the following problem. The algorithm and analysis hereof can be extended to the problem in the question easily.

$A$ is a sorted array of $n$ integers. $B$ is an array of $m$ integers. $n\gt0, m\gt0$.

How can we merge them into one array efficiently without changing the order of elements in $B$ so that the result array has minimum number of inversions?


As OP indicated, the problem above can be done trivially in $O(nm)$. "For each element in $A$ 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." The OP also noted that in the result array, we should keep elements that come from $A$ sorted.

The observations above given by OP lead to the following recursive helper algorithm that gives the indices where elements of $A$ should be inserted into $B$. The simple idea is "binary insertion". That is, insert the middle element into $B$, then recurse.

Pythonic notations will be used.

Input: $A$ is an array with $A[sa\colon ea]$ sorted. $B$ is another array with subarray $B[sb\colon eb]$ specified. $I$ is an array of the same length as $A$.
Output: updated $I$, such that if for each element $A[i]$ in $A[sa\colon ea]$, we insert $A[i]$ right before $B[I[i]]$, keeping the original order of $A$ among themself, the inversion number of $A[sa\colon ea]$ merged with $B[sb\colon eb]$ is minimized.
Procedure:

  1. If $sa\ge ea$, return.
  2. Let $ma = (sa + ea)//2$
  3. Scan through $B[sb\colon eb]$ to find the indice $mb$ in range($sb\colon eb+1$) such that if we put $A[ma]$ right before $B[mb]$, we will have minimum number of inversions that consist of $A[ma]$ and an element in $B[sb\colon eb]$. (Or, any one of those optimal indices).
  4. Let $I[ma] = mb$.
  5. Call this procedure with $A[sa\colon ma-1]$, $B[sb\colon mb]$ and $I$.
  6. Call this procedure with $A[ma+1\colon sb]$, $B[mb\colon eb]$ and $I$.

To solve the initial problem, we will do the following.

  1. Initialize $I$, an array of $n$.
  2. Run the algorithm above with $A[0\colon n]$, $B[0\colon m]$ and $I$
  3. Merge $A$ with $B$ according to $I$.
  4. Return the merged array.

If implemented properly, the algorithm above runs in $O(m\log n + n\log m)$ time. It can be proved that $O(m\log n + n\log m)$ time is optimal. It uses $O(n)$ auxiliary space.

The algorithm here is, basically, doing the same thing to find the same arrangement as in OP's pesudocode. Only more efficiently.

It is a nice exercise to prove the correctness of either algorithm.


If the given array $A$ is not sorted, then sort it at the start of the algorithm. That will add $O(n\log n)$ to its time-complexity.

$\endgroup$
1
  • $\begingroup$ Thanks for figuring this out. The answer is along the lines I was thinking, but refined to actually work. I'm curious about two things: 1) I generally get the idea that either the optimal inversions is central, reducing m multiplicatively, but requiring a "full recurse of n" or it's an extreme reducing n multiplicatively, but requiring more scans of m, but I'm curious how you do the analysis to show this (a simple textbook pointer would be helpful). 2) Do you have any hints on how to show it's optimality? $\endgroup$ – Erik May 27 at 3:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.