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.