• Let the permutation be $\pi \equiv (3 9 2 5 6 7 10 11 13 15 14 16 12 1 4 8)$.
• Split into runs: $r_1:(3 9)$, $r_2:(2 5 6 7 10 11 13 15)$, $r_3:(14 16)$, $r_4:(12)$, $r_5:(1 4 8)$.
• The runs begin at indeces $p[1] = 1$, $p[2] = 3$, $p[3] = 11$, $p[4] = 13$, $p[5] = 14$. Total number of runs is $R=5$.
• Encode each number in $[1..15]$ by the run to which it belongs to. This is us mapping the integer $k$ to $run(\pi^{-1}(k))$.
• We get that:

1 -> run 5 | (1 4 8)2 -> run 2 | (2 5 ... 15)3 -> run 1 | (3 9)4 -> run 5 | (1 4 8)--5 -> run 2 | (2 5 ... 15)6 -> run 2 | (2 5 ... 15)7 -> run 2 | (2 5 ... 15)8 -> run 5 | (1 4 8)--9 -> run 1 | (3 9)10 -> run 2| (2 5 ... 15)11 -> run 2| (2 5 ... 15)12 -> run 4| (12)--13 -> run 2| (2 5 ... 15)14 -> run 3| (14 16)15 -> run 2| (2 5 ... 15)16 -> run 3| (14 16)

• This gives us the array $S = [5, 2, 1, 5| 2, 2, 2, 5| 1, 2, 2, 4| 2, 3, 2, 3]$
• The $k$th occurrence of symbol $s$ in $S$ corresponds to the row of the permutation $P[s] + k$. The occurrence will be at $\pi(P[s] + k)$.
• Suppose we want to find $\pi(P[s] + k) = y$.

§ Relationship to burrows wheeler?

• See that we do sort of the same thing, where we identify a string based on the ranks of its characters?!