Can we sort without permutations?

Question

It is well-known that sorting permutations by transposition is in $\sf{P}$, as the minimum number of transpositions required to sort $\pi \in S_n$ is exactly $inv(\pi) = \{ (i,j) \in [n] \times [n] : i < j \text{ and } \pi(i) > \pi(j) \}$. This notion of "inversion number" has also applications in algebraic combinatorics, for instance it allows to endow $S_n$ with a structure of lattice, called the permutohedron and based on the weak Bruhat order.

It can be illuminating to recast the problem in group-theoretic terms. We are given a group $G$ with generator set $\Gamma$ and a mapping $i_G : \Gamma^* \rightarrow G$, and another group $H$ on which $G$ acts transitively, and we want to solve the following problem: given $h \in H$, find a minimum-length $w \in \Gamma^*$ such that $i_G(w).h = 1_H$. In the permutation case, $G = H = S_n$ and $\Gamma$ is the set of transpositions.

Question: are there other instances of this problem which admit efficient algorithms?

Answer 1

I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to this wikipedia entry we can define it as follows. Let $X$ be a group, and let $H$ denote the set of tuples $(x_1,\ldots,x_n) \in X^n$ such that $x_1 \ldots x_n = 1_X$. If we let $G$ be the braid group $B_n$ generated by the moves $\sigma_i$, we can define an action of $B_n$ over $H$ by:

$\sigma_i(x_1,\ldots,x_n) = (x_1,\ldots,x_{i-1},x_{i+1},x_{i+1}^{-1} x_i x_{i+1},\ldots,x_n).$

That is to say, $\sigma_i$ combines the effect of a swap and a conjugation at positions $i$ and $i+1$. It might be possible to solve this problem optimally in polynomial time, which would answer to your question.

Answer 2

The following paper by Mark Jerrum studied the problem you mentioned when $G=H=S_n$ and $G=H=A_n$ (the alternating group):

• Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985) http://dx.doi.org/10.1016/0304-3975(85)90047-7 .

Among other results, he proved that when $G=H=S_n$ and $\Gamma$ is the set of "cyclically adjacent transpositions," the minimum length of such $w$ can be found in polynomial time.