Computer Science – Data Structures and Algorithms
Scientific paper
2009-09-12
Computer Science
Data Structures and Algorithms
40 pages, 2 figures. Derived from J. Kelleher's Ph.D thesis, Encoding Partitions as Ascending Compositions, University College
Scientific paper
Integer partitions may be encoded as either ascending or descending compositions for the purposes of systematic generation. Many algorithms exist to generate all descending compositions, yet none have previously been published to generate all ascending compositions. We develop three new algorithms to generate all ascending compositions and compare these with descending composition generators from the literature. We analyse the new algorithms and provide new and more precise analyses for the descending composition generators. In each case, the ascending composition generation algorithm is substantially more efficient than its descending composition counterpart. We develop a new formula for the partition function p(n) as part of our analysis of the lexicographic succession rule for ascending compositions.
Kelleher Jerome
O'Sullivan Barry
No associations
LandOfFree
Generating All Partitions: A Comparison Of Two Encodings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Generating All Partitions: A Comparison Of Two Encodings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generating All Partitions: A Comparison Of Two Encodings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-477394