Consider the permutation graph below:
Let's say I only have the amount of numbers in the permutation. 5, in this case, and all intersections between the first and the second parallel lines, like {2,5},{2,4}, and {2,3}, for example.
With only this information, is it possible to figure out the original one-liner permutation that defines this graph, which is {4,3,5,1,2}, I think?
Thank you very much :)
Yes, it is possible to reconstruct the permutation based on the total number of elements and the list of "intersections" (these correspond to inversions in the original permutation).
In fact, even less information would be sufficient: we can reconstruct the permutation if, for each number $i$, we know just the count $C(i)$ of numbers smaller than $i$ that intersect with $i$ (we don't need to know which specific numbers it intersects with). In your example, it would be enough to know that $C(1)=C(2)=0$, $C(3)=C(5)=2$ and $C(4)=3$.
The permutation will be built in steps. Starting with an empty list, in $i$-th step we insert number $i$ into the existing list at the right spot, so that the relative ordering of numbers in the list will be the same as in the full permutation. Since by that time we have already placed numbers $1$ to $(i-1)$ in the list and they are already in the correct positions relative to each other, the intersections between the newly-added number and existing ones must be consecutive and on the right-hand side of the list. Thus, we just need to skip $C(i)$ positions from the right before we insert number $i$ (so if $C(i)=0$, we append number $i$ at the end of the list).
In your example, we would build the list as follows: $$\begin{array}{lcl} C(1)=0 & \rightarrow & \mathbf{1} & \\ C(2)=0 & \rightarrow & 1, \mathbf{2} & \\ C(3)=\fbox{2} & \rightarrow & \mathbf{3}, \fbox{1, 2}\\ C(4)=\fbox{3} & \rightarrow & \mathbf{4}, \fbox{3, 1, 2}\\ C(5)=\fbox{2} & \rightarrow & 4, 3, \mathbf{5}, \fbox{1, 2}\\ \end{array}$$
