# Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees +
## 4 Discussion  
In this article, we have demonstrated the possibilities of using the method based on AND/OR trees to obtain combinatorial generation algorithms for combinatorial sets of several well-known lattice paths. In particular, the following lattice paths were considered: North-East lattice paths, Dyck paths, Delannoy paths, Schroder paths, and Motzkin paths. For each of these combinatorial sets of lattice paths, there is an expression of its cardinality function that belongs to the algebra \(\{\mathbb{N},+,\times,R\}\). This fact made it possible to construct AND/OR tree structures for these combinatorial sets, in which the number of their variants is equal to the number of objects in the combinatorial set. To associate each considered lattice path with one specific variant of the corresponding AND/OR tree structure, the bijection rules were derived. Applying the constructed AND/OR tree structures, we have developed algorithms for ranking and unranking their variants. All developed algorithms have a recursive form since the applied AND/OR tree structures were built by using recurrence relations. The developed algorithms, together with the obtained bijection rules, make it possible to encode a given lattice path as a single number (by applying ranking algorithms). For example, this reduces the amount of data stored if it is necessary to store information about a large number of lattice paths. It is also possible to recover each lattice path by decoding the corresponding rank (by applying unranking algorithms). In addition, the unranking algorithms make it possible to form a sample of random lattice paths with the given properties by applying them to random rank values. If it is necessary to generate all objects with the given parameters (for example, when an exhaustive search is needed to solve an optimization problem), then we can run the unranking algorithm for all rank values. Furthermore, the exhaustive generation can be performed by sequentially traversing all variants of the considered AND/OR tree structure. The developed combinatorial generation algorithms for lattice paths have polynomial time complexity, which is determined by the maximum number of recursive calls (the height of an AND/OR tree), the maximum number of child nodes of a given node (the width of an AND/OR tree), and the computational complexity of calculating the value of the cardinality function. Assuming algebraic operations with numbers in \(O(1)\), the performed computational experiments confirmed the obtained theoretical estimation of asymptotic computational complexity for the developed ranking and unranking algorithms. To reduce the time complexity of these algorithms, we can add a preliminary step where all the required values of the cardinality function are calculated and stored. In this case, the computational complexity of algorithms will depend only on the size of the AND/OR tree structure. However, this improvement requires additional memory space. In addition, if an AND/OR tree structure contains OR nodes where the number of children depends on the AND/OR tree parameters (for example, as AND/OR trees for \(C_{n}\), \(S_{n}\) and \(M_{n}\)), then the computational complexity of ranking and unranking algorithms can be reduced as follows:  
* By calculating \(sum\) (for example, see Line 5 in Algorithm 3 or Lines 5-14 in Algorithm 4), applying a simpler explicit formula without using the summation operator;
* By a preliminary search of the value of the selected child of the OR node (for example, the parameter \(I\) defined in Lines 6-14 in Algorithm 4), applying an approximate formula (as in [26]). Thus, the main contribution of this article is the derivation of bijections between two sets of discrete structures (the set of lattice paths and the set of AND/OR tree variants), as well as new algorithms for their generation.