Permutation codes

There are many analogies between subsets and permutations of a set, and in particular between sets of subsets and sets of permutations. The theories share many features, but there are also big differences. This paper is a survey of old and new results about sets (and groups) of permutations, concentrating on the analogies and on the relations to coding theory. Several open problems are described.


There are many analogies between sets of subsets of {1,…,n}{1,…,n} and sets of permutations of {1,…,n}{1,…,n}.

In both cases, the objects can be represented by lists of length nn (with entries {0,1}{0,1} for subsets or {1,…,n}{1,…,n} for permutations, where a permutation is represented in passive form).

In each case, there is a metric structure (Hamming distance) for the lists (where d(x,y)d(x,y) is the number of positions where xx and yy differ) and an algebraic structure (addition mod 2 or symmetric difference for subsets, composition for permutations).