Previous Article in Journal
An Adaptive Spectral Clustering Algorithm Based on the Importance of Shared Nearest Neighbors

Article

# From Enumerating to Generating: A Linear Time Algorithm for Generating 2D Lattice Paths with a Given Number of Turns

by
Department of Marketing Management, Takming University of Science and Technology, Neihu District, Taipei 11451, Taiwan
Algorithms 2015, 8(2), 190-208; https://0-doi-org.brum.beds.ac.uk/10.3390/a8020190
Received: 19 December 2014 / Revised: 27 April 2015 / Accepted: 30 April 2015 / Published: 8 May 2015
We propose a linear time algorithm, called G2DLP, for generating 2D lattice L(n1, n2) paths, equivalent to two-item multiset permutations, with a given number of turns. The usage of 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 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 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 turns, for example, a decreasing order or an increasing order. In practice, two applications, scheduling and cryptography, are discussed. View Full-Text
Show Figures

Figure 1

MDPI and ACS Style

Kuo, T. From Enumerating to Generating: A Linear Time Algorithm for Generating 2D Lattice Paths with a Given Number of Turns. Algorithms 2015, 8, 190-208. https://0-doi-org.brum.beds.ac.uk/10.3390/a8020190

AMA Style

Kuo T. From Enumerating to Generating: A Linear Time Algorithm for Generating 2D Lattice Paths with a Given Number of Turns. Algorithms. 2015; 8(2):190-208. https://0-doi-org.brum.beds.ac.uk/10.3390/a8020190

Chicago/Turabian Style

Kuo, Ting. 2015. "From Enumerating to Generating: A Linear Time Algorithm for Generating 2D Lattice Paths with a Given Number of Turns" Algorithms 8, no. 2: 190-208. https://0-doi-org.brum.beds.ac.uk/10.3390/a8020190

Find Other Styles

### Article Access Map by Country/Region

1
Only visits after 24 November 2015 are recorded.
Search more from Scilit