  It is well-known that the Toffoli gate and the negation gate together yield a
universal gate set, in the sense that every permutation of $\{0,1\}^n$ can be
implemented as a composition of these gates. Since every bit operation that
does not use all of the bits performs an even permutation, we need to use at
least one auxiliary bit to perform every permutation, and it is known that one
bit is indeed enough. Without auxiliary bits, all even permutations can be
implemented. We generalize these results to non-binary logic: If $A$ is a
finite set of odd cardinality then a finite gate set can generate all
permutations of $A^n$ for all $n$, without any auxiliary symbols. If the
cardinality of $A$ is even then, by the same argument as above, only even
permutations of $A^n$ can be implemented for large $n$, and we show that indeed
all even permutations can be obtained from a finite universal gate set. We also
consider the conservative case, that is, those permutations of $A^n$ that
preserve the weight of the input word. The weight is the vector that records
how many times each symbol occurs in the word. It turns out that no finite
conservative gate set can, for all $n$, implement all conservative even
permutations of $A^n$ without auxiliary bits. But we provide a finite gate set
that can implement all those conservative permutations that are even within
each weight class of $A^n$.
