Analysis of an Enumeration Algorithm for Unordered K-partitions of N

Files
TR Number
CS74009-R
Date
1974
Journal Title
Journal ISSN
Volume Title
Publisher
Department of Computer Science, Virginia Polytechnic Institute & State University
Abstract

In many combinatorial problems, the need to compute the number of unrestricted partitions of n or to enumerate over the set of unrestricted partitions of n occurs frequently. Let two positive integers k and n be given, the set of unordered k-tup1es (a1,a2,..., ak) of positive integers such that a1+a2+...+ak=n is called the unordered k-partitions of n. In this paper, an algorithm to enumerate the set is presented and analyzed. The running time of the algorithm is shown to be linearly proportional to the number of elements in the set. The number of unordered k-partitions of n, f_k(n), is given in a recurrence relation as a byproduct. With these results, to enumerate the unrestricted partitions of n, we need only to enumerate successfully the unordered 1- partition of n, 2-partitions of n, ... , up to n-partitions of n.

Description
Keywords
Citation