From enumerating to generating: a linear time algorithm for generating 2D lattice paths with a given number of turns (Q1736650)

Summary: We propose a linear time algorithm, called \textbf{G2DLP}, for generating 2D lattice \(L(n_1,n_2)\) paths, equivalent to two-item \(\{A^{n_1},B^{n_2}\}\) multiset permutations, with a given number of \textit{turns}. The usage of \textit{turn} has three meanings: in the context of multiset permutations, it means that two consecutive elements of a permutation belong to two different items; in lattice path enumerations, it means that the path changes its direction, either from eastward to northward or from northward to eastward; in open shop scheduling, it means that we transfer a job from one type of machine to another. The strategy of \textbf{G2DLP} is divide-and-combine; the division is based on the enumeration results of a previous study and is achieved by aid of an integer partition algorithm and a multiset permutation algorithm; the combination is accomplished by a concatenation algorithm that constructs the paths we require. The advantage of \textbf{G2DLP} is twofold. First, it is optimal in the sense that it directly generates all feasible paths without visiting an infeasible one. Second, it can generate all paths in any specified order of \textit{turns}, for example, a decreasing order or an increasing order. In practice, two applications, scheduling and cryptography, are discussed.