Efficient Uniform Sampling of Surjections via their Profiles

Arnaud Carayol, Pablo Rotondo

In this article, we develop efficient sampling algorithms for random surjections from $[n]$ to $[k]$ for all $n\ge k$. We make no assumption about $n$ and $k$. In particular, we…