A map $f:[n]^{\ell}\to[n]^{n}$ has locality $d$ if each output symbol
in $[n]=\{1,2,\ldots,n\}$ depends only on $d$ of the $\ell$ input
symbols in $[n]$. We show that the output distribution of a $d$-local
map has statistical distance at least $1-2\cdot\exp(-n/\log^{c^{d}}n)$
from a uniform permutation of $[n]$. This seems to be the first lower
bound for the well-studied problem of generating permutations. Because
$\poly(n)$-size AC$^{0}$ circuits can sample almost uniform permutations,
the result also separates AC$^{0}$ sampling from local.

As an application, we prove that any cell-probe data structure for
storing permutations $\pi$ of $n$ elements such that $\pi(i)$ can
be retrieved with $d$ non-adaptive probes must use space $\ge\log_{2}n!+n/\log^{c^{d}}n$
. This is arguably the first lower bound for a natural data structure
problem that is obtained from a sampling lower bound.