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.