Given a distribution over $[n]^n$ such that any $k$ coordinates need $k/\log^{O(1)}n$ bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality $\Omega(\log(n/k)/\log\log(n/k))$. In particular, we show that for any constant $\delta>0$, there exists $\varepsilon=2^{-\Omega(n^{1-\delta})}$ such that $\Omega(\log n/\log\log n)$ non-adaptive cell probes on uniform cells are required to:
- Sample a uniformly random permutation on $n$ elements with error $1-\varepsilon$. This provides an exponential improvement on the $\Omega(\log\log n)$ cell probe lower bound by Viola.
- Sample an $n$-vector with each element independently drawn from a random $n^{1-\delta}$-vector, with error $1-\varepsilon$. This provides the first adaptive vs non-adaptive cell probe separation for sampling.

The major technical component in our proof is a new combinatorial theorem about flower with small kernel, i.e. a collection of sets where few elements appear more than once. We show that in a family of $n$ sets, each with size $O(\log n/\log\log n)$, there must be $k=\mathrm{poly}(n)$ sets where at most $k/\log^{O(1)}n$ elements appear more than once.

To show the lower bound on sampling permutation, we also prove a new $\Omega(k)$ communication lower bound on sampling uniformly distributed disjoint subsets of $[n]$ of size $k$, with error $1-2^{-\Omega(k^2/n)}$. This result unifies and subsumes the lower bound for $k=\Theta(\sqrt{n})$ by Ambainis et al., and the lower bound for $k=\Theta(n)$ by Göös and Watson.