An Efficient Generic Algorithm for the Generation of Unlabelled Cycles
Conrado Martı́nez, Xavier Molinero · Birkhäuser Basel eBooks · 2004
In this paper we combine two recent generation algorithms to obtain a new generic algorithm for the generation of all unlabelled cycles with components from some class A and total size n. Sawada’s algorithm [ 13 ] lists all k-ary unlabelled cycles with fixed content that is the number of occurrences of each symbol is fixed and given a priori. The other algorithm [ 8 ], by the authors generates all multisets of objects with given total size n from any admissible unlabelled class A. By admissible we mean that the class can be specified using the E-class , atomic classes disjoint 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 unlabelled admissible class A. 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 A to which the objects in the cycle belong . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.