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.
2018
Random and Exhaustive Generation of Combinatorial Structures 2018
GASCom 2018 Random Generation of Combinatorial Structures
Atene (Grecia)
18-20 Giugno 2018
Elena barcucci, Antonio Bernini, Renzo Pinzani
File in questo prodotto:
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.

Utilizza questo identificatore per citare o creare un link a questa risorsa: https://hdl.handle.net/2158/1136748
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? ND
social impact