The two well-known approaches to designing combinatorial generation algorithms are the recursive approach and the iterative approach. In this thesis a third design approach using coroutines, introduced by Knuth and Ruskey, is explored further. An introduction to coroutines and their implementation in modern languages (in particular Python) is provided, and the coroutine-based approach is introduced using an example, and contrasted with the recursive and iterative approaches. The coroutine sum, coroutine product, and coroutine symmetric sum constructs are defined to create an algebra of coroutines, and used to give concise definitions of coroutine-based algorithms for generating ideals of chain and forest posets. Afterwards, new coroutine-based variations of several algorithms, including the Steinhaus-Johnson-Trotter algorithm for generating permutations in Gray order, the Varol-Rotem algorithm for generating linear extensions in Gray order, and the Pruesse-Ruskey algorithm for generating signed linear extensions of a poset in Gray order, are given. / Graduate / 0984 / saba@uvic.ca
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/5879 |
| Date | 29 January 2015 |
| Creators | Saba, Sahand |
| Contributors | Ruskey, Frank |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web, http://creativecommons.org/licenses/by-sa/2.5/ca/ |
Page generated in 0.011 seconds