In this project the student will undertake a thorough research of existing approaches for generating permutations of multisets (unique permutations of sets whose elements may be repeated). New techniques will also be investigated. The main practical goal will be a Matlab/Octave toolbox for permutation generation.
I expect that a potential student taking up this project will be up for the challenge and be mature both as a programmer and in terms of their genuine interest in maths/combinatorics.
Efficiently generating permutations of a set of arbitrary cardinality is a challenging but essentially solved problem since 1888 (Laisant). There are two basic types of algorithms: those that generate all permutations as a sequence (ie one permutation is generated from a previous one), and those that rank and unrank permutations (ie they implement the mapping between an integer between 1 and n! and a permutation, according to some ordering). The latter is more desirable and powerful, as for instance it makes it trivial the generation of permutations uniformly at random.
However the efficient generation of permutations of a multiset of arbitrary cardinality has only been tackled in recent years (both for sequential and ranked permutations generation). A number of approaches have been proposed by mathematical researchers. On the other hand, other proposals come from the field of source coding (compression). The student task will be to investigate and understand in depth the most relevant results, and then implement them in a neatly written and well documented Matlab/Octave toolbox. The goal is a toolbox that will cover fairly comprehensively the topic of permutations generation . This will allow for straightforward empirical comparisons between existing approaches, which are currently lacking.
Permutations are everywhere, and thus a well-written and usable toolbox can have an important practical impact in a number of fields.