## 1 Introduction  
It is common to find ourselves confronted with problems in which an exhaustive examination of all solutions is necessary or desirable [1]. However, we do not want to use brute force to go through all possible solutions. Therefore, there is a clear need to design an efficient algorithm that can eliminate certain cases from consideration. More than this, our goal is to design an optimal algorithm, whereby all infeasible solutions can be ignored. That is, it directly generates all feasible solutions without visiting any infeasible solutions. For example, we have proposed an algorithm for generating all permutations of {1, 2,..., _n_} with a given number of inversions, while never visiting any of the unqualified permutations [2]. In most applications of permutation generation we are interested in minimizing the total running time, not the maximum time between successive visits [1]. In this study, by utilizing the enumeration results of a previous study [3] and the method of integer partition, we propose an optimal algorithm for generating 2D lattice \(L(n_{1},\,n_{2})\) paths according to a given number of _turns_. It identically generates two-item {A\({}^{n}\), B\({}^{n_{2}}\)} _multiset permutations_ according to a given number of _turns_. Herein, 2D lattice \(L(n_{1},\,n_{2})\) denotes an integer rectangular lattice that has a horizontal \(x\)-axis and a vertical \(y\)-axis. A path is a route that starts at point (0, 0) then moves through a succession of steps, usually under the step set {\(<\)1, 0\(>\), \(<\)0, 1\(>\)}, and finally ends at the target point (\(n_{1},\,n_{2}\)). In other words, after leaving the starting point (0, 0), the path can apply unit steps only eastward or northward, but can change direction at any point (\(x,\,y\)) until it reaches the target point (\(n_{1},\,n_{2}\)). Some studies deal with an under-diagonal path that only contains points (\(x,\,y\)) with \(\,x\geq y\,\), for example [4]. Some studies deal with a higher dimensional lattice, for example [5]. For a comprehensive survey on the topic of lattice paths, please see [6]. The word \"_multiset_\" (often shortened to _mset_) which abbreviates the term \"multiple-membership set\", is now the commonly accepted name for replacing \"bag\", \"bunch\", \"weighted set\", \"occurrence set\", \"heap\", \"sample\", and \"fireset\" [7]. A _multiset_ is a set such that each item in the set has a multiplicity that specifies how many times the item repeats, and the cardinality of a _multiset_ is the sum of the multiplicities of its all items. In short, a _multiset_ is a set with repeated items. Obviously, a set is a special case of _multiset_ in which each item occurs only once. Multisets are of interest in mathematics, physics, philosophy, logic, linguistics and computer science [7]. Many studies have been devoted to _multiset_ permutations [8, 9, 10, 11, 12, 13, 14, 15]. However, we know of no published algorithms for generating _multiset_ permutations with a given number of _turns_. There are various motivations behind the interest in the _turn_ enumeration of lattice paths. [PERSON] described three motivations from probability, statistics, and commutative algebra, respectively [16]. He also showed the wide diversity of connections and applications in other domains like combinatorics, representation theory, and q-series. The motivation of our studies on the topic of lattice path was inspired by trying to solve a kind of _open shop_ scheduling problem that is concerned with setup time among different types of machines [17]. Here, setup time means the delay time that occurs when we arrange the processing route (or path) of a job from one type of machine to another. This kind of _open shop_ scheduling problem is, intrinsically, a multiset permutation problem, while the latter is, essentially, a lattice path enumeration problem. Therefore, in this study, _turn_ has three meanings.