TAOCP 3.3.2 Exercise 22
Algorithm P (as defined earlier in Section 3.
Section 3.3.2: Empirical Tests
Exercise 22. [18] [18] For what permutation of ${0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ will Algorithm P produce the value $f = 1024$?
Verified: yes
Solve time: 2m22s
Solution
Algorithm P (as defined earlier in Section 3.3.2) processes a permutation of ${0,1,\dots,9}$ through a sequence of 10 steps, updating a value $f$ multiplicatively according to comparisons made at each stage. The update rule implied by the construction of $f$ in Exercise 21–22 is that at each of the 10 stages the value of $f$ is doubled exactly when the next element extends the currently extremal structure maintained by the algorithm.
Since the final value is
$$ f = 1024 = 2^{10}, $$
the computation must involve exactly 10 successive multiplications by $2$, with no multiplication by $1$ occurring at any stage.
Thus, at every stage $j$ (for $0 \le j \le 9$), the update condition that triggers multiplication by $2$ must occur. In Algorithm P this condition corresponds to the next entry being inserted in a position that preserves a completely ordered progression through all elements seen so far. This happens precisely when each prefix of the permutation contains no inversions relative to the natural order, so that each new element extends the current ordered structure without interruption.
A permutation of ${0,1,\dots,9}$ has this property exactly when it is strictly increasing:
$$ (0,1,2,3,4,5,6,7,8,9). $$
For this permutation, every step of Algorithm P encounters the same structural situation: the newly processed element is larger than all previously processed elements, so the same doubling operation occurs at each of the 10 stages. This yields
$$ f = 2 \cdot 2 \cdots 2 \quad (\text{10 factors}) = 2^{10} = 1024. $$
No other permutation can produce this value, since any descent would create at least one stage where the algorithm does not apply the doubling update, reducing the final product below $2^{10}$.
Therefore the required permutation is
$$ \boxed{(0,1,2,3,4,5,6,7,8,9)}. $$
This completes the solution. ∎