# Combinatorial Generation Algorithms for Some Lattice Paths Using the Method Based on AND/OR Trees +
## 3 Results
### Computational Experiments  
We have also performed a computational experiment aimed at testing the obtained computational complexity of the developed ranking and unranking algorithms. For this purpose, we implemented these algorithms in the computer algebra system Maxima [25] on a laptop (Intel i7-9750H, 2.6 GHz, Windows 10, 64 bit). We then measured the elapsed time of the algorithms for ranking and unranking variants of the AND/OR trees for \(L_{m}^{m}\), \(C_{n}\), \(D_{m}^{m}\), \(S_{n}\) and \(M_{n}\) with different values of the parameters \(n\) and \(m\). All calculations were made for the variants of the AND/OR trees with the maximum rank (because this is usually the hardest case to compute due to the need to traverse the entire AND/OR tree structure). For the maximum rank \(r:=L_{m}^{m}-1\), Algorithms 1 and 2 have polynomial time complexity \(O(nm)\) for \(m<n\) and \(O(n^{2})\) for \(n<m\). Figure (a)a presents the average time for unranking and ranking such variants of the AND/OR tree for \(L_{m}^{m}\) where \(m=100\) and \(n\) is in the range of 5 to 200 with step 5. This figure confirms polynomial time complexity \(O(n^{2})\) for \(n<100\) and linear time complexity \(O(n)\) for \(n>100\) when \(m=100\). Figure (b)b presents the average time for unranking and ranking variants of the AND/OR tree for \(L_{m}^{m}\) where \(n=100\) and \(m\) is in the range of 5 to 200 with step 5. This figure confirms linear time complexity \(O(m)\) for \(m<100\) and constant time complexity \(O(1)\) for \(m>100\) when \(n=100\). For other fixed values of \(m\) (or \(n\)), the general form of the dependence on \(n\) (or \(m\)) does not change. For the maximum rank \(r:=C_{n}-1\), Algorithms 3 and 4 have polynomial time complexity \(O(n^{3})\). Figure 17 presents the average time for unranking and ranking such variants of the AND/OR tree for \(C_{n}\) where \(n\) is in the range of 1 to 50 with step 1. This figure confirms polynomial time complexity \(O(n^{3})\). Figure 16: Average time for unranking (**blue**) and ranking (**red**) variants of the AND/OR tree for \(L_{m}^{m}\): (**a**) dependence on \(n\) when \(m=100\); and (**b**) dependence on \(m\) when \(n=100\). For the maximum rank \(r:=D_{n}^{m}-1\), Algorithms 5 and 6 have the following polynomial time complexity (due to all special cases of the calculation of Equation (5)): \(O(m^{3})\) for \(2m<n\), \(O(m^{2}(n-m))\) for \(m<n<2m\), \(O(n^{2}(m-n))\) for \(n<m<2n\), and \(O(n^{3})\) for \(2n<m\). Figure 18a presents the average time for unranking and ranking such variants of the AND/OR tree for \(D_{n}^{m}\) where \(m=50\) and \(n\) is in the range of 5 to 200 with step 5. Figure 18b presents the average time for unranking and ranking variants of the AND/OR tree for \(D_{n}^{m}\) where \(n=50\) and \(m\) is in the range of 5 to 200 with step 5. These figures confirm the derived polynomial time complexity for all special cases. For other fixed values of \(m\) (or \(n\)), the general form of the dependence on \(n\) (or \(m\)) does not change. Figure 17: Average time for unranking (**blue**) and ranking (**red**) variants of the AND/OR tree for \(C_{n}\). Figure 18: Average time for unranking (**blue**) and ranking (**red**) variants of the AND/OR tree for \(D_{n}^{m}\): (**a**) dependence on \(n\) when \(m=50\); and (**b**) dependence on \(m\) when \(n=50\). For the maximum rank \(r:=S_{n}-1\), Algorithms 7 and 8 have polynomial time complexity \(O(n^{4})\). Figure 19 presents the average time for unranking and ranking such variants of the AND/OR tree for \(S_{n}\) where \(n\) is in the range of 1 to 50 with step 1. This figure confirms polynomial time complexity \(O(n^{4})\). For the maximum rank \(r:=M_{n}-1\), Algorithms 9 and 10 have polynomial time complexity \(O(n^{4})\). Figure 20 presents the average time for unranking and ranking such variants of the AND/OR tree for \(M_{n}\) where \(n\) is in the range of 1 to 50 with step 1. This figure confirms polynomial time complexity \(O(n^{4})\).