<p>I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to <a href="http://en.wikipedia.org/wiki/Braid_group">this wikipedia entry</a> 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:</p>

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

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

CC BY-SA 3.0
2014-04-02T20:14:41.667Z
2014-04-02T20:26:39.280Z
2014-04-02T20:26:39.280Z
NisaiVloot
<p>The following paper by Mark Jerrum studied the problem you mentioned when $G=H=S_n$ and $G=H=A_n$ (the alternating group):</p>

<ul>
<li>Mark Jerrum: The Complexity of Finding Minimum-Length Generator Sequences. Theor. Comput. Sci. 36: 265-289 (1985) <a href="http://dx.doi.org/10.1016/0304-3975(85)90047-7" rel="noreferrer">http://dx.doi.org/10.1016/0304-3975(85)90047-7</a> .</li>
</ul>

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

CC BY-SA 3.0
2014-04-03T12:43:26.130Z
2014-04-03T12:43:26.130Z
Yoshio Okamoto
<p>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 &lt; j \text{ and } \pi(i) &gt; \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.</p>

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

<p>Question: are there other instances of this problem which admit efficient algorithms?</p>

CC BY-SA 3.0
2014-04-03T12:09:43.610Z
Well, the problem is probably easy when $G=\prod_i Z_{r_i}$
greg
<sorting>
Can we sort without permutations?
NisaiVloot
# Can we sort without permutations?

(Asked by: username_0 on 2014-04-02)

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?

**Tags:** sorting

> **Comments:**
> **username_1**: Well, the problem is probably easy when $G=\prod_i Z_{r_i}$  

---

## 2 answers

### Answer by username_0 on 2014-04-02. Score: 6

I don't have a definite answer to your question, but "braid sorting" seems a possible candidate. According to [this wikipedia entry](http://en.wikipedia.org/wiki/Braid_group) 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 by username_2 on 2014-04-03. Score: 5

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.


---

