<p>While reading the post, <a href="https://cstheory.stackexchange.com/questions/25427/probability-of-generating-a-desired-permutation-by-random-swaps"><em>Probability of generating a desired permutation by random swaps</em>, by Aaronson</a>, I got interested in restricted sorting problem:</p>
<p>If we restrict sorting algorithms to use transpositions (swapping integers in two non-adjacent positions) and restrict the number of transpositions then some sequences are sortable and others are not.</p>
<p>Note that sequence <span class="math-container">$A$</span> may contain some <strong>repeated</strong> integers</p>
<p>Formally, the problem is:</p>
<p><strong>Input</strong>: a sequence <span class="math-container">$A=[a_1, a_2, ..., a_{2N}]$</span> of <span class="math-container">$2N$</span> positive (possibly repeated) integers.</p>
<p><strong>Question</strong>: Is it possible to sort sequence <span class="math-container">$A$</span> using <span class="math-container">$N$</span> transpositions of non-adjacent positions?</p>
<blockquote>
<p>Is there a polynomial-time algorithm to solve this problem? Or Is it NP-complete?</p>
</blockquote>
<p>This was post on <a href="https://mathoverflow.net/questions/191539/recognizing-sequences-sortable-by-transpositions">MathOverflow</a>.</p>
<p>P.S. This problem has a nice geometric interpretation: It is equivalent to deciding the existence of a path of length at most N between two points on a special <a href="https://en.wikipedia.org/wiki/Permutohedron" rel="nofollow noreferrer">2N-Permutahedron</a>.</p>
<p>Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one <em>non-adjacent</em> transposition.</p>
<p><a href="https://i.sstatic.net/Fs1D5.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Fs1D5.jpg" alt="Permutahedron of order 4" /></a></p>
<p><strong>Edit</strong>: I am interested in the case where the input sequence <span class="math-container">$A$</span> is restricted to permutation of <span class="math-container">$[1,2,3, …, 2N]$</span>. Is it efficiently solvable under this restriction?</p>

CC BY-SA 3.0
2014-12-16T15:07:01.560Z
By two non-adjacent elements, do you mean two elements which need not be adjacent? If that's what you mean, there's a polynomial-time algorithm for it. If you mean they must not be adjacent, I don't know the answer.
Peter Shor 
CC BY-SA 3.0
2014-12-16T15:11:24.277Z
@PeterShor Let $a_i$ and $a_j$ two elements in $A$. There are non-adjacent if $|i-j| \gt 1$.
Mohammad Al-Turkistany
CC BY-SA 3.0
2014-12-16T15:15:49.103Z
@PeterShor I mean that the two elements must not be adjacent in $A$ as shown above.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-12T05:33:34.750Z
If we allowed adjacent transpositions, we'd need exactly $2N-c(\pi)$ transpositions to express $\pi$, where $c(\pi)$ is the number of cycles in the cycle decomposition of $\pi$ (see http://cstheory.stackexchange.com/q/4096/5038).  Given a cycle $\sigma=(a_1,a_2,\dots,a_k)$, let its badness $b(\sigma)$ be the number of pairs $(a_1,a_2)$, $(a_2,a_3)$, ..., $(a_{k-1},a_k)$, $(a_k,a_1)$ that are adjacent.  Let $b'(\pi)$ be the number of cycles in the cycle decomposition of $\pi$ whose badness is $\ge 2$.  Then you need at least $2N-c(\pi)+b'(\pi)$ non-adjacent transpositions to express $\pi$.
D.W.
CC BY-SA 3.0
2015-08-12T06:33:42.580Z
@D.W. Thanks for the link. I am just interested in the complexity of the problem :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-12T15:34:14.360Z
This doesn't answer the question, but seems potentially related: inversion-(nearly)-optimal sorting by [Elmasry & Fredman](http://dx.doi.org/10.1007/s00236-007-0061-0)
Joshua Grochow
CC BY-SA 3.0
2018-01-11T01:46:57.670Z
It can be solved using one of these two methods ... 1-Characteristic polynomial
2- Horner's method
Wafa
<cc.complexity-theory><sorting>
Efficient recognition of sequences sortable by transpositions?
Mohammad Al-Turkistany
# Efficient recognition of sequences sortable by transpositions?

(Asked by: username_0 on 2014-12-16)

While reading the post, [*Probability of generating a desired permutation by random swaps*, by Aaronson](https://cstheory.stackexchange.com/questions/25427/probability-of-generating-a-desired-permutation-by-random-swaps), I got interested in restricted sorting problem:

If we restrict sorting algorithms to use transpositions (swapping integers in two non-adjacent positions) and restrict the number of transpositions then some sequences are sortable and others are not.

Note that sequence $A$ may contain some **repeated** integers

Formally, the problem is:

**Input**: a sequence $A=[a\_1, a\_2, ..., a\_{2N}]$ of $2N$ positive (possibly repeated) integers.

**Question**: Is it possible to sort sequence $A$ using $N$ transpositions of non-adjacent positions?

> Is there a polynomial-time algorithm to solve this problem? Or Is it NP-complete?

This was post on [MathOverflow](https://mathoverflow.net/questions/191539/recognizing-sequences-sortable-by-transpositions).

P.S. This problem has a nice geometric interpretation: It is equivalent to deciding the existence of a path of length at most N between two points on a special [2N-Permutahedron](https://en.wikipedia.org/wiki/Permutohedron).

Special permutahedron means that two nodes are connected by an edge if and only if the corresponding permutations are separated by one *non-adjacent* transposition.

[![Permutahedron of order 4](https://i.sstatic.net/Fs1D5.jpg)](https://i.sstatic.net/Fs1D5.jpg)

**Edit**: I am interested in the case where the input sequence $A$ is restricted to permutation of $[1,2,3, …, 2N]$. Is it efficiently solvable under this restriction?

**Tags:** cc.complexity-theory, sorting
> **Comments:**
> **username_1**: By two non-adjacent elements, do you mean two elements which need not be adjacent? If that's what you mean, there's a polynomial-time algorithm for it. If you mean they must not be adjacent, I don't know the answer.  
> **username_0**: @PeterShor Let $a_i$ and $a_j$ two elements in $A$. There are non-adjacent if $|i-j| \gt 1$.  
> **username_0**: @PeterShor I mean that the two elements must not be adjacent in $A$ as shown above.  
> **username_2**: If we allowed adjacent transpositions, we'd need exactly $2N-c(\pi)$ transpositions to express $\pi$, where $c(\pi)$ is the number of cycles in the cycle decomposition of $\pi$ (see http://cstheory.stackexchange.com/q/4096/5038).  Given a cycle $\sigma=(a_1,a_2,\dots,a_k)$, let its badness $b(\sigma)$ be the number of pairs $(a_1,a_2)$, $(a_2,a_3)$, ..., $(a_{k-1},a_k)$, $(a_k,a_1)$ that are adjacent.  Let $b'(\pi)$ be the number of cycles in the cycle decomposition of $\pi$ whose badness is $\ge 2$.  Then you need at least $2N-c(\pi)+b'(\pi)$ non-adjacent transpositions to express $\pi$.  
> **username_0**: @D.W. Thanks for the link. I am just interested in the complexity of the problem :)  
> **username_3**: This doesn't answer the question, but seems potentially related: inversion-(nearly)-optimal sorting by [Elmasry & Fredman](http://dx.doi.org/10.1007/s00236-007-0061-0)  
> **username_4**: It can be solved using one of these two methods ... 1-Characteristic polynomial 2- Horner's method  

---

## 0 answers

