I'm trying to generate random bitonic sequences to test bitonic merging/sorting networks. However I'm unable to come up with a good way to actually generate different types of these sequences with equal likelihood.
A sequence $x_0, x_1, \ldots, x_{n-1}$ is bitonic if,
$\exists $ $k$ such that $x_0 \leq x_1 \leq \ldots, x_{k-1} \leq x_k \geq x_{k+1} \geq \ldots \geq x_{n-1}$
$\exists$ $k$ such that $x_0 \geq x_1 \geq \ldots, x_{k-1} \geq x_k \leq x_{k+1} \leq \ldots \leq x_{n-1}$
a circular shift of any of the above types
My best attempt so far is to randomly permute an input, say $0, 1, \ldots, n-1$, and then pass it through a bitonic sorter and stop before the final merge. However this is a little expensive and I'm trying to find better ways to generate them.
Let's say you just want to generate a bitonic permutation of $\{1,2,\dots,n\}$. To do this, we should figure out what bitonic permutations look like.
Given any bitonic permutation, we can cyclic-shift it to get a bitonic permutation beginning with $1$. The result looks like $$1 < x_1 < x_2 < \dots < x_k < n > y_1 > y_2 > \dots > y_{n-k-2}$$ for some $k$, where $x_1, x_2, \dots, x_k$ and $y_1, y_2, \dots, y_k$ are the elements of $\{2, \dots, n-1\}$ in some order. It's possible that either the $x$ sequence or the $y$ sequence is actually empty.
Actually, if I tell you the sets $X =\{x_1, \dots, x_k\}$ and $Y = \{y_1, \dots, y_{n-k-2}\}$, there is only one way to compute the bitonic permutation above, because the elements of $X$ must be in ascending order and the elements of $Y$ must be in descending order.
So we can generate a uniformly random bitonic permutation by randomly choosing each element of $\{2, \dots, n\}$ to be either part of $X$ or part of $Y$. Having done that, we put the elements in their now-uniquely-determined places, and get a sequence of the above form. We finish by applying a random cyclic shift.