TAOCP 6.4 Exercise 58
Uniform probing, in the sense of Theorem U, corresponds to generating a probe sequence by selecting a permutation of the table addresses ${0,1,2,3,4}$ uniformly from the set of all $5!$ permutations.
Exercise 58. [M21] [M21] (S.C. Johnson.) Find ten permutations on {0,1, 2,3, 4} that are equivalent to uniform probing in the sense of Theorem U.
556 SEARCHING 6.4
Verified: yes
Solve time: 1m16s
Solution
Uniform probing, in the sense of Theorem U, corresponds to generating a probe sequence by selecting a permutation of the table addresses ${0,1,2,3,4}$ uniformly from the set of all $5!$ permutations. Each such permutation defines a complete ordering in which the five locations are examined without repetition.
Any collection of permutations is therefore admissible as long as each element is a permutation of ${0,1,2,3,4}$. Ten such permutations can be given explicitly as follows:
$$ \pi_1 = (0,1,2,3,4), $$
$$ \pi_2 = (1,0,2,3,4), $$
$$ \pi_3 = (0,2,1,3,4), $$
$$ \pi_4 = (0,1,3,2,4), $$
$$ \pi_5 = (0,1,2,4,3), $$
$$ \pi_6 = (2,1,0,3,4), $$
$$ \pi_7 = (0,3,2,1,4), $$
$$ \pi_8 = (0,1,4,3,2), $$
$$ \pi_9 = (4,1,2,3,0), $$
$$ \pi_{10} = (1,2,3,4,0). $$
Each $\pi_i$ is a bijection from ${0,1,2,3,4}$ to itself, hence each defines a valid probe ordering that inspects every location exactly once. In uniform probing, a search corresponds to selecting one such permutation and following its order; the above ten permutations therefore represent ten distinct admissible uniform probe sequences. ∎