Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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 ?

share|improve this question
3  
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 –  Yoshio Okamoto Feb 15 '13 at 23:51
    
I just have edited my question by extending the notion of inversion for words. –  Samuele Giraudo Feb 16 '13 at 10:08
1  
I agree that any stable sorting algorithm will work. –  JɛffE Feb 16 '13 at 16:58
2  
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. –  Tsuyoshi Ito Feb 16 '13 at 20:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.