On O(1) Time Algorithms for Combinatorial Generation
Liming Xiang · The Computer Journal · 2001
Takaoka has recently proposed two loopless algorithms for generating well formed parenthesis strings with length $2n$ and combinations $\mathcal{C}(r,n)$ of $n$ elements out of $r$ elements, respectively. O(1) time algorithms for generating $\mathcal{C}(r,n)$ in canonical representation that were found in the literature cannot list combinations with the Strong Minimal Change Property (SMCP), Eades and McKay's algorithm can generate $\mathcal{C}(r,n)$ in canonical representation with SMCP, but needs O$(n)$ worst-case time per combination. In this paper, we mainly discuss some orders with SMCP for $\mathcal{C}(r,n)$ in canonical representation, and give a loopless algorithm to generate $\mathcal{C}(r,n)$ in canonical representation with SMCP. We also give a loopless algorithm to list well formed parenthesis strings with length $2n$. Our two algorithms are more efficient in both space and time than Takaoka's two algorithms, respectively. In addition, our algorithms can be modified easily to generate objects in some different orders.