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

$\endgroup$
  • 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$ – Peter Shor Dec 16 '14 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$ – Mohammad Al-Turkistany Dec 16 '14 at 15:11
  • $\begingroup$ @PeterShor I mean that the two elements must not be adjacent in $A$ as shown above. $\endgroup$ – Mohammad Al-Turkistany Dec 16 '14 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 '15 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 '15 at 5:33

protected by Community Mar 26 '18 at 14:01

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Browse other questions tagged or ask your own question.