While reading the post, Probability of generating a desired permutation by random swaps, by Aaronson, 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.
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.
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.
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?