  The problem of storing permutations in a distributed manner arises in several
common scenarios, such as efficient updates of a large, encrypted, or
compressed data set. This problem may be addressed in either a combinatorial or
a coding approach. The former approach boils down to presenting large sets of
permutations with \textit{locality}, that is, any symbol of the permutation can
be computed from a small set of other symbols. In the latter approach, a
permutation may be coded in order to achieve locality. This paper focuses on
the combinatorial approach.
  We provide upper and lower bounds for the maximal size of a set of
permutations with locality, and provide several simple constructions which
attain the upper bound. In cases where the upper bound is not attained, we
provide alternative constructions using Reed-Solomon codes, permutation
polynomials, and multi-permutations.
