TAOCP 5.1.1 Exercise 1

Let the permutation be written in one-line form $a_1 a_2 \cdots a_9$.

taocpmathematicsalgorithmsvolume-3

Section 5.1.1: Inversions

Exercise 1. [**] [10] What is the inversion table for the permutation 271845936? What permutation has the inversion table 50121200?

Verified: yes
Solve time: 48m13s

Let the permutation be written in one-line form $a_1 a_2 \cdots a_9$.

1. Inversion table of $271845936$

We compute

$$ b_i = #{, j < i : a_j > a_i ,}. $$

Permutation:

$$ (2,7,1,8,4,5,9,3,6). $$

  • $i=1$, $a_1=2$: none before, $b_1=0$.
  • $i=2$, $a_2=7$: none larger before, $b_2=0$.
  • $i=3$, $a_3=1$: $2,7$ are larger, $b_3=2$.
  • $i=4$, $a_4=8$: none larger, $b_4=0$.
  • $i=5$, $a_5=4$: $7,8$ are larger, $b_5=2$.
  • $i=6$, $a_6=5$: $7,8$ are larger, $b_6=2$.
  • $i=7$, $a_7=9$: none larger, $b_7=0$.
  • $i=8$, $a_8=3$: $7,8,4,5,9$ are larger, $b_8=5$.
  • $i=9$, $a_9=6$: $7,8,9$ are larger, $b_9=3$.

Thus the inversion table is

$$ \boxed{002022053}. $$

2. Permutation with inversion table $50121200$

Let

$$ (b_1,\dots,b_8) = (5,0,1,2,1,2,0,0). $$

In TAOCP inversion-table reconstruction, we build the permutation by inserting $k = 8,7,\dots,1$ into position $b_k+1$ among the already constructed sequence.

Start with an empty list.

  • $k=8$, $b_8=0$: insert at position 1

$[8]$

  • $k=7$, $b_7=0$: insert at position 1

$[7,8]$

  • $k=6$, $b_6=2$: insert at position 3

$[7,8,6]$

  • $k=5$, $b_5=1$: insert at position 2

$[7,5,8,6]$

  • $k=4$, $b_4=2$: insert at position 3

$[7,5,4,8,6]$

  • $k=3$, $b_3=1$: insert at position 2

$[7,3,5,4,8,6]$

  • $k=2$, $b_2=0$: insert at position 1

$[2,7,3,5,4,8,6]$

  • $k=1$, $b_1=5$: insert at position 6

$[2,7,3,5,4,1,8,6]$

Therefore the required permutation is

$$ \boxed{27354186}. $$

Final answers

  • Inversion table of $271845936$: $\boxed{002022053}$
  • Permutation for $50121200$: $\boxed{27354186}$