The design of efficient dynamic programming and transfer matrix enumeration algorithms

作者：Conway Andrew R^*

来源：Journal of Physics A-Mathematical and Theoretical, 2017, 50(35): 353001.

DOI：10.1088/1751-8121/aa8120

• combinatorics
• lattice models
• enumeration
• algorithm
• transfer matrix

Many algorithms have been developed for enumerating various combinatorial objects in time exponentially less than the number of objects. Two common classes of algorithms are dynamic programming and the transfer matrix method. This paper covers the design and implementation of such algorithms.
A host of general techniques for improving efficiency are described. Three quite different example problems are used for detailed examples: 1324 pattern avoiding permutations, three-dimensional polycubes (using a novel approach), and two-dimensional directed animals. Other examples from the literature are used when appropriate to describe applicability of various techniques, but the paper does not attempt to survey all applications.

• 出版日期2017-9-1