6
$\begingroup$

The input to our problem is a pair of strings, say $x$ and $y$. We treat our alphabet size as a constant, i.e., our input is effectively a pair of arrays with the values therein bounded by a constant.

The problem is to compute the number of adjacent swaps (done to either of the strings), to make the strings equal. It is easy to see that our problem is equivalent to making $y$ equal to $x$.

One simple approach that I can think of is that we can first compute the appropriate permutation that makes $y$ into $x$ (easy to do in linear time) and then count number of inversions therein. Straightforward algorithms for inversion counting yield us $\mathcal{O}(n \lg n)$ overall running time. Chan and Pătraşcu show that this can be improved to $\mathcal{O}(n\sqrt{\lg n})$ if we use the fact that we deal with the special case of a permutation.

However, in the case of strings, we still have a bit more information than in the aforementioned case: our permutation comes from a pair of arrays with a constant number of possible values, whereas in the case of a permutation, the numbers can be $\mathcal{O}(n)$.

For example, in the case of a binary alphabet, I believe that the maximum number of swaps needed (inversions) is $\frac{n(n-1)}{4}$, so half the number possible in case of an arbitary permutation.

Moreover, in the case of equal number of zeros and ones (which I'm guessing would be the most complicated one), we have only ~ ${n\choose{n/2}} = \frac{n!}{\left(\frac{n}{2}!\right)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\lg\left(\frac{n!}{\left(\frac{n}{2}!\right)^2}\right) = \Theta(n)$, in contrast to $\lg(n!) = \Theta(n\lg n)$. Therefore, simple counting lower bounds similar to that question would also not seem to apply.

Are better algorithms known for this special case?

$\endgroup$
3
  • $\begingroup$ Do yu want to compute the number of swaps or execute the swaps? Are you sure you can consider very small alphabets (like binary) or is the alphabet size just a parameter "left out"? $\endgroup$
    – vonbrand
    Aug 30 '21 at 1:14
  • $\begingroup$ @vonbrand Is "yes" a valid answer? I'm mainly interested in just counting the number of swaps in a string from a constant-sized, but not necessarily binary alphabet. That said, if the sequence of swaps can also be then reconstructed and/or there is some special trick that works only in the case of a binary alphabet and/or we can have an exact analysis that includes alphabet size, I'd be happy (and interested) to see those too :) $\endgroup$
    – MeyCJey
    Aug 30 '21 at 5:15
  • $\begingroup$ The straightforward approach you propose seems to me correct, although I have no proof. ffiw: notice you may assume that the two strings differ on the first element, so you will definitely need to bring the first occurrence of $y[1]$ in $x$ all the way to the front. You might as well do those permutations first. Now we have two strings whose first character is equal, so we consider only $x[2\ldots n]$ and $y[2\ldots n]$. Iterate until $|x|=0$. But I have no proof of my claim that "we might as well do those permutations first". This allows you to both count and perform the permutations. $\endgroup$ Sep 8 '21 at 16:02
1
$\begingroup$

The answer is yes, as a linear-time algorithm is possible if the alphabet size is constant. I explain a $\Theta(k n)$-time algorithm here, where $k$ is the size of the alphabet.

It is easier to see the problem if the permutation is represented as a bipartite graph on the plane, like this image (ignore the upper graph). The edge set is $E = \{(i,p_i)\}_i$. The inversions are same as intersections between two edges: $\{ (i,p_i), (j, p_j) \in E \mid i < j \land p_i > p_j \}$.

First, notice that if the edge set is partitioned into $k$ sets for each alphabet, then each edge subset is monotone. That is, two edges can only intersect between different alphabets. Let $E^a$ to denote the edge subset of alphabet $a$.

We can count the number of intersections between two edge subsets $E^a, E^b$ in a linear time. The algorithm iterates the edges in a subset $E^a$. The edges in $E^b$ intersecting to an edge in $E^a$ can be represented as a (possibly empty) interval. Furthermore, the endpoints of the intervals can only go up during the iteration. Thus, by maintaining the endpoints of the intersecting interval, this subproblem can be solved in $\Theta(|E^a| + |E^b|)$ time.

Pseudocode is as follows:

def count_intersections(as, bs):
  # Loop invariant: (l, r) are endpoints of the intersecting interval such that
  # (l <= j < r) if and only if as[i] and bs[j] intersect.
  l, r = 0, 0
  total = 0
  for i in 0..len(as):
    while r < len(bs) && bs[r].1 < as[i].1:
      r += 1
    while l < r && !(as[i].0 < bs[l].0):
      l += 1
    total += r - l
  return total

The answer is the sum of all answers of such subproblems for each pair of edge sets. Because each edge occurs in at most $k$ subproblems, and the edge sets can be constructed in $O(n + k)$ time, the running time of the algorithm is $O(k n)$.

$\endgroup$
1
  • $\begingroup$ Thank you, that's a fantastic answer! Simple algorithm and a clear explanation--the graph perspective does make the approach pretty intuitive. $\endgroup$
    – MeyCJey
    Dec 22 '21 at 12:54

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.