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.

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?

share|improve this question
    
Well, the problem is probably easy when $G=\prod_i Z_{r_i}$ –  mobius dumpling Apr 3 at 12:09

2 Answers 2

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.

share|improve this answer

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

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.

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.