Combinatorial Generation by Fusing Loopless Algorithms

Takaoka, T. and Violich, S.

    Some combinatorial generation problems can be bro- ken into subproblems for which loopless algorithms already exist. We discuss means by which loop- less algorithms can be fused to produce a new loop- less algorithm that solves the original problem. We demonstrate this method with two new loopless algo- rithms, MIXPAR and MULTPERM. MIXPAR gen- erates well-formed parenthesis strings containing two different types of parentheses. MULTPERM gener- ates multiset permutations in linear space using only arrays; it is simpler and more efficient than the recent algorithm of Korsh and LaFollette (2004).
Cite as: Takaoka, T. and Violich, S. (2006). Combinatorial Generation by Fusing Loopless Algorithms. In Proc. Twelfth Computing: The Australasian Theory Symposium (CATS2006), Hobart, Australia. CRPIT, 51. Gudmundsson, J. and Jay, B., Eds. ACS. 69-77.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS