Exhaustive generation of some lattice paths and their prefixes

We refer to positive lattice 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 Motzkin and Schroder paths and their prefixes, according to their length. For each kind of paths we define a recursive algorithm as well as an iterative one, specifying which path follows a given one in the lexicographic order. Furthermore we study the complexity of these algorithms by using the relations between the number of paths of a given size and the number of final north-east or south-east steps. (C) 2020 Elsevier B.V. All rights reserved.