An Efficient generic algorithm for the generation of unlabelled cycles
Visualitza/Obre
Estadístiques de LA Referencia / Recolecta
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/97029
Tipus de documentReport de recerca
Data publicació2003-06-06
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
In this report 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 A. 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 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.
CitacióMartinez, C., Molinero, X. "An Efficient generic algorithm for the generation of unlabelled cycles". 2003.
Forma partLSI-03-35-R
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
R03-35.pdf | 92,85Kb | Visualitza/Obre |