Return to Question

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!}{(\frac{n}{2}!)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\lg(\frac{n!}{(\frac{n}{2}!)^2}) = \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?

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?

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!}{(\frac{n}{2}!)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\Theta\big(\lg(\frac{n!}{(\frac{n}{2}!)^2})\big) = \Theta(n)$, in contrast to $\Theta\big(\lg(n!)\big) = \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?

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!}{(\frac{n}{2}!)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\lg(\frac{n!}{(\frac{n}{2}!)^2}) = \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?

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!}{(\frac{n}{2}!)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\Theta\big(log(\frac{n!}{(\frac{n}{2}!)^2})\big) = \Theta(n)$, in contrast to $\Theta(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?

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!}{(\frac{n}{2}!)^2}$ possible inputs to our algorithm, instead of $n!$. Correspondingly, we have $\Theta\big(\lg(\frac{n!}{(\frac{n}{2}!)^2})\big) = \Theta(n)$, in contrast to $\Theta\big(\lg(n!)\big) = \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?