Modification of the algorithm development method for combinatorial generation based on the application of the generating functions theory

Download article in PDF format

Authors: Shablya Yu. V., Kruchinin D. V.

Annotation: In this article, a modification of the method for developing algorithms for combinatorial generation on the basis of and-or trees is presented. In contrast to the original version of the method, the proposed modification uses the method aimed at obtaining explicit expressions for the coefficients of generating functions. This method is applied to find an expression of the cardinality function of a combinatorial set by using the known expression of the generating function for the sequence of values of this cardinality function.

Keywords: combinatorial generation, and-or tree, generating function, method, ranking, unranking