We refer to lattice positive paths as to paths in the discrete plane constituted by different kinds of steps (north-east, east and south-east), starting from the origin and never going under the x-axis. They have been deeply studied both from a combinatorial and an algorithmic point of view. We propose some algorithms for the exhaustive generation of positive paths which are prefixes of Dyck, Motzkin and q-coloured Motzkin paths, according to their length. For each kind of path we define a recursive version as well an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of hese algorithms by using the relations between the number of paths of given size and the number of north-east steps appearing in the final rise.
Exhaustive generation of positive lattice paths / Elena barcucci, Antonio Bernini, Renzo Pinzani. - ELETTRONICO. - 2113:(2018), pp. 79-86. (Intervento presentato al convegno GASCom 2018 Random Generation of Combinatorial Structures tenutosi a Atene (Grecia) nel 18-20 Giugno 2018).
Exhaustive generation of positive lattice paths
Elena barcucci;Antonio Bernini;Renzo Pinzani
2018
Abstract
We refer to lattice positive paths as to paths in the discrete plane constituted by different kinds of steps (north-east, east and south-east), starting from the origin and never going under the x-axis. They have been deeply studied both from a combinatorial and an algorithmic point of view. We propose some algorithms for the exhaustive generation of positive paths which are prefixes of Dyck, Motzkin and q-coloured Motzkin paths, according to their length. For each kind of path we define a recursive version as well an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of hese algorithms by using the relations between the number of paths of given size and the number of north-east steps appearing in the final rise.File | Dimensione | Formato | |
---|---|---|---|
Exhaustive generation of positive lattice paths.pdf
Accesso chiuso
Tipologia:
Pdf editoriale (Version of record)
Licenza:
Tutti i diritti riservati
Dimensione
380.4 kB
Formato
Adobe PDF
|
380.4 kB | Adobe PDF | Richiedi una copia |
BARCUCCI_BERNINI_PINZANI_LOC_PROC2.pdf
accesso aperto
Descrizione: Local proceedings
Tipologia:
Altro
Licenza:
Tutti i diritti riservati
Dimensione
231.24 kB
Formato
Adobe PDF
|
231.24 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.