Packing regularity of permutation codes

Permutation codes have been extensively investigated, both because of their intrinsic mathematical interest and because of relevant applications based on error-correcting codes. The Maximum Permutation Code Problem (MPCP) is a challenging packing problem on permutations. The objective is to maximize the size of permutation codes with a given minimum Hamming distance between the codewords. In a similar way to the well-known sphere packing problem, an optimal permutation packing usually has a highly regular structure. In this paper a new idea of regularity degree of permutation codes is developed and the relationship between packing density and regularity degree of permutation codes is investigated. Computational experiments on random permutation packings run on different MPCPs confirm that, analogously to the sphere packing problem, the regularity degree of permutation codes tends to increase as the code size approaches to the optimum.