A Unified Approach to Algorithms Generating Unrestricted and Restricted Integer Compositions and Integer Partitions

An original algorithm is presented that generates both restricted integer compositions and restricted integer partitions that can be constrained simultaneously by (a) upper and lower bounds on the number of summands (“parts”) allowed, and (b) upper and lower bounds on the values of those parts. The...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematical modelling and algorithms 2010-03, Vol.9 (1), p.53-97
Main Author: Opdyke, John Douglas (J.D.)
Format: Article
Language:English
Subjects:
Algorithms
Data Mining and Knowledge Discovery
Integer programming
Management Science
Mathematical analysis
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research
Optimization
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An original algorithm is presented that generates both restricted integer compositions and restricted integer partitions that can be constrained simultaneously by (a) upper and lower bounds on the number of summands (“parts”) allowed, and (b) upper and lower bounds on the values of those parts. The algorithm can implement each constraint individually, or no constraints to generate unrestricted sets of integer compositions or partitions. The algorithm is recursive, based directly on very fundamental mathematical constructs, and given its generality, reasonably fast with good time complexity. A general, closed form solution to the open problem of counting the number of integer compositions doubly restricted in this manner also is presented; its formulaic link to an analogous solution for counting doubly-restricted integer partitions is shown to mirror the algorithmic link between these two objects.
ISSN:1570-1166
2214-2487
1572-9214
2214-2495
DOI:10.1007/s10852-009-9116-2