Packing regularity of permutation codes

János Barta, Roberto Montemanni, Derek Smith

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)86-92
Number of pages7
JournalLecture Notes in Management Science
Publication statusE-pub ahead of print - 31 Dec 2015


  • Coding theory
  • Combinatorial Optimisation
  • Discrete geometry
  • Permutation codes
  • Sphere packing


Dive into the research topics of 'Packing regularity of permutation codes'. Together they form a unique fingerprint.

Cite this