1
$\begingroup$

I currently have a problem, whose solution requires to remove from a permutation of $\lbrace 1,\ \dots,\ n\rbrace$ those values that are to the left of a smaller one.

My idea was to remove the complement of the longest increasing subsequence, but am not quite sure, if that yields the correct result (which I doubt, because the longest increasing subsequence need not be unique, whereas the inversion relation is) and/or whether it would be the most efficient way to remove all inversions.

Questions:

  • does the longest increasing subsequence of a permutation represent the complement of all inversions?

  • what is the fastest known algorithm for removing all "inverted" elements from a permutation?

$\endgroup$
7
  • $\begingroup$ The answer to the first question is certainly "no", as the permutation $[2,3,1,6,4,5]$ shows: in this case, the longest increasing subsequence is even unique, it is $2,3,4,5$. If I understand correctly, you want to remove $2$,$3$ and $6$, right? $\endgroup$ Commented Apr 20, 2017 at 6:51
  • $\begingroup$ @MartinRubey yes, you have put it correctly; I want to remove 2,3 and 6. And thanks for the example with unique longest increasing subsequence. $\endgroup$ Commented Apr 20, 2017 at 6:54
  • $\begingroup$ Find the smallest element $s_1=1$. Find the smallest element $s_2$ that comes after $s_1$; find smallest $s_3$ that comes after $s_2$, etc. until you get $s_k$ equal the last element in the permutation. Then $(s_1,s_2,\dots,s_k)$ is the required subpermutation, isn't it? $\endgroup$ Commented Apr 20, 2017 at 21:26
  • $\begingroup$ @MaxAlekseyev your algorithm will work, but you always would have to search for the next smallest unremoved elemement; could require $O(n^2)$ steps or, you could use a second array with values $[1,\ \dots,\ n]$, in which the removed elements are marked; in that array you could go from left to right to identify the next smallest element and then remove all elements of the primary array until you have encountered the identified next minimal value, requiring $O(n)$ steps. $\endgroup$ Commented Apr 21, 2017 at 5:00
  • $\begingroup$ @ManfredWeis: So, there is a linear algorithm. What is your question then? $\endgroup$ Commented Apr 21, 2017 at 12:12

1 Answer 1

2
$\begingroup$

Create a doubly-linked list $L$, initially empty. Scan a given permutation $p=(p_1,p_2,\dots,p_n)$ from left to right, and for each element $p_i$ perform the following operations:

  1. (loop) While $L$ is not empty and $p_i$ is smaller than the last element of $L$, remove this last element from $L$.

  2. Append $p_i$ to $L$.

At the end, $L$ will contain a required subpermutation of $p$. Notice that visiting (i.e., comparison to) every element of $L$ results in either appending or removal of an element to/from $L$. The total number of such operations does not exceed $2n$, since every element of $p$ may be appended to $L$ only once and removed from $L$ only once. So, this is a linear-time algorithm.

$\endgroup$
2
  • $\begingroup$ does "last element" denote the element to the left of $p_i$ or the element at the end of the list? $\endgroup$ Commented Apr 21, 2017 at 19:26
  • $\begingroup$ "last element" refers to the last element of $L$ $\endgroup$ Commented Apr 21, 2017 at 21:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .