Combinatorial generation by fusing loopless algorithms
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).