AAAI Publications, Eighth Symposium on Abstraction, Reformulation, and Approximation

Font Size: 
Modelling Equidistant Frequency Permutation Arrays in Constraints
Ian Philip Gent, Paul McKay, Ian Miguel, Peter William Nightingale, Sophie Huczynska

Last modified: 2009-10-22


Equidistant Frequency Permutation Arrays are combinatorial objects of interest in coding theory. A frequency permutation array is a type of constant composition code in which each symbol occurs the same number of times in each codeword. The problem is to find a set of codewords such that any pair of codewords are a given uniform Hamming distance apart. The equidistant case is of special interest given the result that any optimal constant composition code is equidistant. This paper presents, compares and combines a number of different constraint formulations of this problem class, including a new method of representing permutations with constraints. Using these constraint models, we are able to establish several new results, which are contributing directly to mathematical research in this area.


constraints; permutation arrays; modelling; combinatorics

Full Text: PDF