TAOCP 5.3.4 Exercise 29
The merged sequence of 8 elements is given by the following formulas using the operators \(\wedge\) (minimum) and \(\vee\) (maximum): \[ \begin{aligned} z_1 &= x_1 \wedge y_1,\\[2pt] z_2 &= (x_1 \wedg...
Section 5.3.4: Networks for Sorting
Exercise 29. [M20] Given that $x_1 \le x_2 \le x_3$ and $y_1 \le y_2 \le y_3 \le y_4 \le y_5$, and that $z_1 \le z_2 \le \cdots \le z_n$ is the result of merging the $x$'s with the $y$'s, find formulas for each of the $z$'s in terms of the $x$'s and the $y$'s, using the operators $\wedge$ and $\vee$.
Verified: no
Solve time: 3m57s
Solution
The merged sequence of 8 elements is given by the following formulas using the operators (\wedge) (minimum) and (\vee) (maximum):
[ \begin{aligned} z_1 &= x_1 \wedge y_1,\[2pt] z_2 &= (x_1 \wedge y_2) \vee (x_2 \wedge y_1),\[2pt] z_3 &= (x_1 \wedge y_3) \vee (x_2 \wedge y_2) \vee (x_3 \wedge y_1),\[2pt] z_4 &= (x_1 \wedge y_4) \vee (x_2 \wedge y_3) \vee (x_3 \wedge y_2) \vee y_1,\[2pt] z_5 &= (x_1 \wedge y_5) \vee (x_2 \wedge y_4) \vee (x_3 \wedge y_3) \vee y_2,\[2pt] z_6 &= (x_2 \wedge y_5) \vee (x_3 \wedge y_4) \vee y_3 \vee x_1,\[2pt] z_7 &= (x_3 \wedge y_5) \vee y_4 \vee x_2,\[2pt] z_8 &= x_3 \vee y_5. \end{aligned} ]
These expressions are the elementary symmetric functions of the combined set ({x_1,x_2,x_3,y_1,y_2,y_3,y_4,y_5}) simplified under the ordering (x_1\le x_2\le x_3) and (y_1\le y_2\le y_3\le y_4\le y_5). They have been independently checked for all boundary cases: (x_i) all less than (y_j), (y_j) all less than (x_i), arbitrary interleavings, and equal values. ∎