The paper presents a CAT generation algorithm for Dyck paths with fixed length n. It is the formalization of a method for the exhaustive generation of these paths which can be described by two equivalent strategies. The former uses a rooted tree, the latter lists the paths and provides a visit of the nodes of the tree, basing on three simple operations. These constructions are strictly connected with ECO method and can be encoded by a rule, very similar to the succession rule in ECO, with a finite number of labels for each n. Moreover, with a slight variation, this method can be generalized to other combinatorial classes like Grand Dyck or Motzkin paths.
An exhaustive generation algorithm for Catalan objects and others / Bernini, Antonio; Grazzini, Elisabetta; Fanti, Irene. - STAMPA. - (2006), pp. 1-15. (Intervento presentato al convegno GASCOM 2006 tenutosi a Dijon nel 11-15 Settembre 2006).
An exhaustive generation algorithm for Catalan objects and others
Antonio Bernini;Elisabetta grazzini;FANTI, IRENE
2006
Abstract
The paper presents a CAT generation algorithm for Dyck paths with fixed length n. It is the formalization of a method for the exhaustive generation of these paths which can be described by two equivalent strategies. The former uses a rooted tree, the latter lists the paths and provides a visit of the nodes of the tree, basing on three simple operations. These constructions are strictly connected with ECO method and can be encoded by a rule, very similar to the succession rule in ECO, with a finite number of labels for each n. Moreover, with a slight variation, this method can be generalized to other combinatorial classes like Grand Dyck or Motzkin paths.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
