(Excerpt)
We discuss an algorithm to generate efficiently all the paths of a two-dimensional lattice with a given number of turns.
The algorithm was first proposed by Ting Kuo, associate professor of the Univeristy of Technology and Science in Takming (Taiwain), and in this paper we will go further with an in depth complexity analysis, implementation and experimental results.
The algorithm performances are then compared against a naive generation approach.
Finally two potential applications of such kind of counting techniques are presented.
The discussed algorithms are all accompained by a modern and reusable C++ implementation.
Given a 2D point lattice, i.e. a grid of points, in this work we will study an efficient way to generate all the paths between two arbitrary points with a given number of turns, that is the paths where the direction of the path changes a given number of times.
In litterature, there are plenty of algorithms and theoretical results about lattice paths generation, but not too many that restrict the enumeration to the paths with a given number of turns.
The motivations to be interested in such counting problems touch a very different set of disciplines such as probability, statistics, cryptography, scheduling, commutative algebra, etc.
The problem of turn enumeration of lattice paths was attacked in many different ways. However there is a uniform approach which is able to handle all these problems, which is by encoding paths in terms of two-rowed arrays.
Actually this is the way in which Narayana, who probably was the first to count paths with respect to their turns, used to see turn enumeration problems.
This study goes from a fairly rigorous complexity analysis to experimentation.
Proudly self-hosted on a cheap Raspberry Pi