<p>Let $(A, \leq)$ be a totally ordered alphabet. </p>

<p>The <em>standardization</em> ${\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 <em>inversion</em> of a word $u$ of length $n$ is a pair $(i, j)$ such that $1 \leq i &lt; j \leq n$ and $u_i &gt; u_j$; since permutations are words with some constraints, this definition also works for permutations).</p>

<p>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$.</p>

<p>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}
  &amp; &amp; a_3 &amp; a_1 &amp; a_4 &amp; a_2 &amp; a_5 &amp; a_7 &amp; a_4 &amp; a_2 &amp; a_3 \\
    &amp;     &amp; 1   &amp;     &amp;     &amp;     &amp;     &amp;     &amp;     &amp;     \\
    &amp;     &amp; 1   &amp;     &amp; 2   &amp;     &amp;     &amp;     &amp;     &amp;     \\
    &amp;     &amp; 1   &amp;     &amp; 2   &amp;     &amp;     &amp;     &amp; 3   &amp;     \\
    &amp; 4   &amp; 1   &amp;     &amp; 2   &amp;     &amp;     &amp;     &amp; 3   &amp;     \\
    &amp; 4   &amp; 1   &amp;     &amp; 2   &amp;     &amp;     &amp;     &amp; 3   &amp; 5   \\
    &amp; 4   &amp; 1   &amp; 6   &amp; 2   &amp;     &amp;     &amp;     &amp; 3   &amp; 5   \\
    &amp; 4   &amp; 1   &amp; 6   &amp; 2   &amp;     &amp;     &amp; 7   &amp; 3   &amp; 5   \\
    &amp; 4   &amp; 1   &amp; 6   &amp; 2   &amp; 8   &amp;     &amp; 7   &amp; 3   &amp; 5   \\
    &amp; 4   &amp; 1   &amp; 6   &amp; 2   &amp; 8   &amp; 9   &amp; 7   &amp; 3   &amp; 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)$.</p>

<p>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 ?</p>

CC BY-SA 3.0
2013-02-15T23:51:19.383Z
How do you define the inversion of a word $u$?  It seems that any stable sorting algorithm will do.  http://en.wikipedia.org/wiki/Sorting_algorithm#Stability
Yoshio Okamoto
CC BY-SA 3.0
2013-02-16T10:08:45.880Z
I just have edited my question by extending the notion of inversion for words.
Samuele Giraudo
CC BY-SA 3.0
2013-02-16T16:58:18.450Z
I agree that any stable sorting algorithm will work.
Jeffε
CC BY-SA 3.0
2013-02-16T20:03:18.633Z
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
<cc.complexity-theory><co.combinatorics><permutations>
Complexity of the standardization
Samuele Giraudo
# Complexity of the standardization

(Asked by: username_0 on 2013-02-15)

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 ?

**Tags:** cc.complexity-theory, co.combinatorics, permutations

> **Comments:**
> **username_1**: How do you define the inversion of a word $u$?  It seems that any stable sorting algorithm will do.  http://en.wikipedia.org/wiki/Sorting_algorithm#Stability  
> **username_0**: I just have edited my question by extending the notion of inversion for words.  
> **username_2**: I agree that any stable sorting algorithm will work.  
> **username_3**: 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.  

---

## 0 answers

