ALCOMFT-TR-03-5

Conrado Mart\'\inez and Xavier Molinero
An Efficient Generic Algorithm for the Generation of Unlabelled Cycles
Barcelona. Work package 4. June 2003.

Abstract: In this paper, we combine two recent generation algorithms to obtain a new algorithm for the generation of unlabelled cycles. Sawada's algorithm lists all k-ary unlabelled cycles with fixed content, that is, the number of occurences of each symbol is fixed and given a priori. The other algorithm, by the authors, generates all multisets of objects with given total size n from any admissible unlabelled class \mathcalA. By admissible we mean that the class can be specificied using atomic classes, disjoints unions, products, sequences, (multi)sets, etc.

The resulting algorithm, which is the main contribution of this paper, generates all cycles of objects with given total size n from any admissible class \mathcalA. Given the generic nature of the algorithm, it is suitable for inclusion in combinatorial libraries and for rapid prototyping. The new algorithm incurs constant amortized time per generated cycle, the constant only depending in the class \mathcalA to which the objects in the cycle belong.

Postscript file: ALCOMFT-TR-03-5.ps.gz (60 kb).