§ Relationship betwee permutations and runs

• 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?!