Is there a "local" algorithm which takes as its input a parking function and returns the non-crossing partition labelled by that sequence?


Background: A parking function is a sequence of positive integers which is a permutation of a sequence $a\_1\leq \ldots \leq a\_n$ satisfying $a\_k \leq k$ for all $k$. In a 1996 article, Richard Stanley showed that there is a bijection between the set of parking functions and the set of maximal chains in the lattice of non-crossing partitions. He gives an algorithm that injectively assigns to each maximal chain a parking function, and then relies on the fact that the two sets have the same cardinality to deduce surjectivity. I'm asking whether in the meantime someone has found an algorithm that produces the inverse function. 


By "local" I mean one that does not have as its first step to label all the maximal chains of non-crossing partitions.



Parking functions to non-crossing partitions
I still hope there is a complete (and easy) answer to the question, but as mentioned in my comment above, and since no one else answered so far, I give a description of the inverse map that is not completely local, but still "better" than first labelling all chains in the noncrossing partition lattice. (I just worked it out briefly, so I am not saying this is the best way of doing it, but it is easy enough to be worked out in 30 min.)


A parking function is called **primitive** if it is weakly increasing. Every parking function can be obtained from a primitive parking function by a series of transpositions of consecutive numbers. E.g.


$$112355 \mapsto 121355 \mapsto 211355 \mapsto 213155 \mapsto 213515 \mapsto 213551.$$


We do not yet have seen here a definition of noncrossing partitions and maximal chains in the noncrossing partition lattice. So observe that a chain in the noncrossing partition lattice can be seen as **factorizations of the long cycle** $(1,2,\ldots,n) \in \mathcal{S}\_n$ into a product of $n$ transpositions $(ij)$. The map from these factorizations to parking functions mentioned above is then the map $\phi$ sending $c = (i\_1j\_1) \ldots (i\_nj\_n)$ to the sequence $(i\_1,\ldots,i\_n)$. In Stanley's article, it is shown that $\phi(factorization)$ is indeed a parking function, and that this map is a bijection. To obtain $\psi := \phi^{-1}$ we must therefore start with a sequence $(i\_1,\ldots,i\_n)$ and turn it into a factorization $c = (i\_1j\_1) \ldots (i\_nj\_n)$.


We do this in two steps: first, we define $\psi$ for primitive parking functions, and then obtain $\psi$ for general parking functions by a sequence of transpositions of factors $(i\_kj\_k)(i\_{k+1}j\_{k+1}) \mapsto (i\_{k+1}j\_{k+1})(i\_k\tilde j\_k)$, such that
$$(i\_kj\_k)(i\_{k+1}j\_{k+1}) = (i\_{k+1}j\_{k+1})(i\_k\tilde j\_k).$$
Observe that this uniquely determines $\tilde j\_k$, and that this is not a valid procedure for any two transpositions. Nonetheless, this works for sequences coming from parking functions.


Let $seq = (i\_1,\ldots,i\_n)$ be a primitive parking function. $\psi(seq)$ is then given by sending the last $1$ in $seq$ to the transposition $(12)$. Afterwards, send the last $i \in 1,2$ to $(i,3)$, then the last $i \in 1,2,3$ to $(i,4)$ and so on.
For example, replacing letters in $112355$ in this way gives
$$
\begin{align\*}
 112355 &\mapsto 1\ (12)\ 2355 \mapsto 1\ (12)(23)\ 355 \mapsto 1\ (12)(23)(34)\ 55 \newline
 &\mapsto (15)(12)(23)(34)\ 55 \mapsto (15)(12)(23)(34)\ 5\ (56) \newline
 &\mapsto (15)(12)(23)(34)(57)(56)
\end{align\*}
$$
It is straightforward to check that this yields indeed a factorization of the long cycle, and by construction, we have $\phi(\ (15)(12)(23)(34)(57)(56)\ ) = 112355$, as desired.


Now, to obtain the parking function $211553$, we first interchange positions $2$ and $3$, and interchange the factors such that $(i\_2j\_2)(i\_3j\_3) = (i\_3j\_3)(i\_2\tilde j\_2)$ so we obtain


$$ \psi( 121355 ) = (15)(23)(13)(34)(57)(56).$$
Here, the third factor became the second, and the second factor $(12)$ turns into $(13)$. We keep going with this procedure and obtain
$$
\begin{align\*}
 \psi(112355) &= (15)(12)(23)(34)(57)(56) \newline
 \psi(121355) &= (15)(23)(13)(34)(57)(56) \newline
 \psi(211355) &= (23)(15)(13)(34)(57)(56) \newline
 \psi(213155) &= (23)(15)(34)(14)(57)(56) \newline
 \psi(213515) &= (23)(15)(34)(57)(14)(56) \newline
 \psi(213551) &= (23)(15)(34)(57)(56)(14).
\end{align\*}
$$
This completes the construction. I didn't present that proof that both steps in the procedure actually work, but they should in fact do.


If someone wants sees a direct way of computing $\psi(213551)$, please post it! And if I should clarify anything, or if someone finds mistakes, please let me know (I haven't yet gone though all details to prove that this procedure works, and I would only do it if this is not yet known, and people are interested).


Best, Christian


