2
$\begingroup$

Let $(A, \leq)$ be a totally ordered alphabet.

The standardization ${\tt std}(u)$ of a word $u \in A^n$ is the unique permutation of $n$ elements having the same inversions as $u$ (recall that an inversion of a word $u$ of length $n$ is a pair $(i, j)$ such that $1 \leq i < j \leq n$ and $u_i > u_j$; since permutations are words with some constraints, this definition also works for permutations).

For instance, let $A$ be the alphabet $\{a_i : i \in \mathbb{N}\}$ where $a_i \leq a_j$ if and only if $i \leq j$ and $u := a_3a_1a_4a_2a_5a_7a_4a_2a_3$. Then, we have ${\tt std}(u) = 416289735$.

To compute ${\tt std}(u)$, an obvious and naive algorithm consists in scanning $u$ from left to right $n$ times and assigning during the $i$th run the letter $i$ to the smallest not yet considerer letter. Applying this to the above example, we obtain \begin{array} & & a_3 & a_1 & a_4 & a_2 & a_5 & a_7 & a_4 & a_2 & a_3 \\ & & 1 & & & & & & & \\ & & 1 & & 2 & & & & & \\ & & 1 & & 2 & & & & 3 & \\ & 4 & 1 & & 2 & & & & 3 & \\ & 4 & 1 & & 2 & & & & 3 & 5 \\ & 4 & 1 & 6 & 2 & & & & 3 & 5 \\ & 4 & 1 & 6 & 2 & & & 7 & 3 & 5 \\ & 4 & 1 & 6 & 2 & 8 & & 7 & 3 & 5 \\ & 4 & 1 & 6 & 2 & 8 & 9 & 7 & 3 & 5 \\ \end{array} showing, assuming that $\leq$ is computable in constant time complexity, that the time complexity of ${\tt std}$ is $\mathcal{O}(n^2)$.

We can do better by using any stable sorting algorithm. The question is what is the best time complexity to compute the standardization of a word ?

$\endgroup$
  • 3
    $\begingroup$ How do you define the inversion of a word $u$? It seems that any stable sorting algorithm will do. en.wikipedia.org/wiki/Sorting_algorithm#Stability $\endgroup$ – Yoshio Okamoto Feb 15 '13 at 23:51
  • $\begingroup$ I just have edited my question by extending the notion of inversion for words. $\endgroup$ – Samuele Giraudo Feb 16 '13 at 10:08
  • 1
    $\begingroup$ I agree that any stable sorting algorithm will work. $\endgroup$ – Jeffε Feb 16 '13 at 16:58
  • 2
    $\begingroup$ This question is equivalent to producing the permutation corresponding to the stably sorted version of a given sequence, and therefore it cannot be solved faster than stable sorting. $\endgroup$ – Tsuyoshi Ito Feb 16 '13 at 20:03

Your Answer

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

Browse other questions tagged or ask your own question.