TAOCP 3.3.2 Exercise 21

**Exercise 3.

taocpmathematicsalgorithmsvolume-1medium

Section 3.3.2: Empirical Tests

Exercise 21. [19] What value of $j$ is indicated by Algorithm P if it is presented with the permutation $(1, 2, 9, 8, 5, 3, 6, 7, 0, 4)$?

Verified: yes
Solve time: 4m40s

Exercise 3.3.2.21 [19]

We are asked to determine the value of $j$ indicated by Algorithm P when presented with the permutation

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

We proceed in strict TAOCP solution-manual style, following Algorithm P from Section 3.3.2, which produces the lexicographic rank of a permutation by incrementally computing $j$ as the rank index.

Step 1: Recall Algorithm P

Algorithm P operates as follows:

  1. Initialize $j \gets 0$.
  2. For $i \gets n-1$ down to $1$ do:
  • Count the number of elements after position $i-1$ that are less than $p_{i-1}$. Call this count $m$.
  • Update $j \gets j + m \cdot (n-i)!$.

Here $p_0, \dots, p_{n-1}$ is the permutation (0-based indexing), and $n = 10$ in this problem.

Step 2: Initialize

Let

$$ p = (1, 2, 9, 8, 5, 3, 6, 7, 0, 4), \quad n = 10, \quad j = 0. $$

We will compute factorials as needed:

$$ 1! = 1, \quad 2! = 2, \quad 3! = 6, \quad 4! = 24, \quad 5! = 120, \quad 6! = 720, \quad 7! = 5040, \quad 8! = 40320, \quad 9! = 362880. $$

Step 3: Iterative computation of $j$

We process $i = 9$ down to $1$ (TAOCP uses 1-based step counting but 0-based indexing for the array):

  1. $i = 9$ ($p_8 = 0$)

Elements after $p_8$: $p_9 = 4$

Count $m = #{x > 8: x < p_8} = #{4 < 0} = 0$

$j \gets 0 + 0 \cdot 1! = 0$ 2. $i = 8$ ($p_7 = 7$)

Elements after $p_7$: $p_8 = 0, p_9 = 4$

$m = #{0,4 < 7} = 2$

$j \gets 0 + 2 \cdot 2! = 0 + 4 = 4$ 3. $i = 7$ ($p_6 = 6$)

Elements after $p_6$: $p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{7,0,4 < 6} = 2$

$j \gets 4 + 2 \cdot 3! = 4 + 12 = 16$ 4. $i = 6$ ($p_5 = 3$)

Elements after $p_5$: $p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{6,7,0,4 < 3} = 1$ (only 0)

$j \gets 16 + 1 \cdot 4! = 16 + 24 = 40$ 5. $i = 5$ ($p_4 = 5$)

Elements after $p_4$: $p_5 = 3, p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{3,6,7,0,4 < 5} = 3$ (3,0,4)

$j \gets 40 + 3 \cdot 5! = 40 + 360 = 400$ 6. $i = 4$ ($p_3 = 8$)

Elements after $p_3$: $p_4 = 5, p_5 = 3, p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{5,3,6,7,0,4 < 8} = 6$

$j \gets 400 + 6 \cdot 6! = 400 + 4320 = 4720$ 7. $i = 3$ ($p_2 = 9$)

Elements after $p_2$: $p_3 = 8, p_4 = 5, p_5 = 3, p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{8,5,3,6,7,0,4 < 9} = 7$

$j \gets 4720 + 7 \cdot 7! = 4720 + 35280 = 40000$ 8. $i = 2$ ($p_1 = 2$)

Elements after $p_1$: $p_2 = 9, p_3 = 8, p_4 = 5, p_5 = 3, p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{9,8,5,3,6,7,0,4 < 2} = 1$ (only 0)

$j \gets 40000 + 1 \cdot 8! = 40000 + 40320 = 80320$ 9. $i = 1$ ($p_0 = 1$)

Elements after $p_0$: $p_1 = 2, p_2 = 9, p_3 = 8, p_4 = 5, p_5 = 3, p_6 = 6, p_7 = 7, p_8 = 0, p_9 = 4$

$m = #{2,9,8,5,3,6,7,0,4 < 1} = 1$ (only 0)

$j \gets 80320 + 1 \cdot 9! = 80320 + 362880 = 443200$

Step 4: Conclusion

The value of $j$ indicated by Algorithm P for the permutation

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

is

$$ \boxed{443200}. $$

This completes the computation. All counts $m$ and factorial multiplications are explicitly justified at each step according to the procedure of Algorithm P.