  In this paper, we introduce polynomial time algorithms that generate random
$k$-noncrossing partitions and 2-regular, $k$-noncrossing partitions with
uniform probability. A $k$-noncrossing partition does not contain any $k$
mutually crossing arcs in its canonical representation and is 2-regular if the
latter does not contain arcs of the form $(i,i+1)$. Using a bijection of Chen
{\it et al.} \cite{Chen,Reidys:08tan}, we interpret $k$-noncrossing partitions
and 2-regular, $k$-noncrossing partitions as restricted generalized vacillating
tableaux. Furthermore, we interpret the tableaux as sampling paths of a
Markov-processes over shapes and derive their transition probabilities.
