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$
  • $\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$ – Martin Rubey Apr 20 '17 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$ – Manfred Weis Apr 20 '17 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$ – Max Alekseyev Apr 20 '17 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$ – Manfred Weis Apr 21 '17 at 5:00
  • $\begingroup$ @ManfredWeis: So, there is a linear algorithm. What is your question then? $\endgroup$ – Max Alekseyev Apr 21 '17 at 12:12
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$
  • $\begingroup$ does "last element" denote the element to the left of $p_i$ or the element at the end of the list? $\endgroup$ – Manfred Weis Apr 21 '17 at 19:26
  • $\begingroup$ "last element" refers to the last element of $L$ $\endgroup$ – Max Alekseyev Apr 21 '17 at 21:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.