11
$\begingroup$

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.

Permutahedron of order 4

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?

$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 16, 2014 at 15:07
  • $\begingroup$ @PeterShor Let $a_i$ and $a_j$ two elements in $A$. There are non-adjacent if $|i-j| \gt 1$. $\endgroup$ Dec 16, 2014 at 15:11
  • $\begingroup$ @PeterShor I mean that the two elements must not be adjacent in $A$ as shown above. $\endgroup$ Dec 16, 2014 at 15:15
  • 1
    $\begingroup$ @PeterShor : $\:$ I thought that was only known for the case in which the elements are all distinct. $\;\;$ $\endgroup$
    – user6973
    Aug 11, 2015 at 23:41
  • $\begingroup$ 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 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$. $\endgroup$
    – D.W.
    Aug 12, 2015 at 5:33

0

Browse other questions tagged or ask your own question.