Computer Science > Data Structures and Algorithms
[Submitted on 5 Jul 2013]
Title:Linear-time generation of specifiable combinatorial structures: general theory and first examples
View PDFAbstract:Various specifiable combinatorial structures, with d extensive parameters, can be exactly sampled both by the recursive method, with linear arithmetic complexity if a heavy preprocessing is performed, or by the Boltzmann method, with complexity Theta(n^{1+d/2}). We discuss a modified recursive method, crucially based on the asymptotic expansion of the associated saddle-point integrals, which can be adopted for a large number of such structures (e.g. partitions, permutations, lattice walks, trees, random graphs, all with a variety of prescribed statistics and/or constraints). The new algorithm requires no preprocessing, still it has linear complexity on average. In terms of bit complexity, instead of arithmetic, we only have extra logarithmic factors. For many families of structures, this provides, at our knowledge, the only known quasi-linear generators. We present the general theory, and detail a specific example: the partitions of n elements into k non-empty blocks, counted by the Stirling numbers of the second kind. These objects are involved in the exact sampling of minimal automata with prescribed alphabet size and number of states, which is thus performed here with average Theta(n ln n) bit complexity, outbreaking all previously known Theta(n^{3/2}) algorithms.
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Connected Papers (What is Connected Papers?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Code, Data and Media Associated with this Article
alphaXiv (What is alphaXiv?)
CatalyzeX Code Finder for Papers (What is CatalyzeX?)
DagsHub (What is DagsHub?)
Gotit.pub (What is GotitPub?)
Hugging Face (What is Huggingface?)
Papers with Code (What is Papers with Code?)
ScienceCast (What is ScienceCast?)
Demos
Recommenders and Search Tools
Influence Flower (What are Influence Flowers?)
CORE Recommender (What is CORE?)
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.