Generating All Partitions: A Comparison Of Two Encodings - Computer Science > Data Structures and AlgorithmsReportar como inadecuado




Generating All Partitions: A Comparison Of Two Encodings - Computer Science > Data Structures and Algorithms - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: Integer partitions may be encoded as either ascending or descendingcompositions for the purposes of systematic generation. Many algorithms existto generate all descending compositions, yet none have previously beenpublished to generate all ascending compositions. We develop three newalgorithms to generate all ascending compositions and compare these withdescending composition generators from the literature. We analyse the newalgorithms and provide new and more precise analyses for the descendingcomposition generators. In each case, the ascending composition generationalgorithm is substantially more efficient than its descending compositioncounterpart. We develop a new formula for the partition function pn as partof our analysis of the lexicographic succession rule for ascendingcompositions.



Autor: Jerome Kelleher, Barry O'Sullivan

Fuente: https://arxiv.org/







Documentos relacionados