Parallel Algorithms for Counting and Randomly Generating Integer Partitions

The full text article is not available for purchase.

The publisher only permits individual articles to be downloaded by subscribers.


This paper presents parallel algorithms for determining the number of partitions of a given integer N , where the partitions may be subject to restrictions, such as being composed of distinct parts, of a given number of parts, and/or of parts belonging to a specified set. We present a series of adaptive algorithms suitable for varying numbers of processors. The fastest of these algorithms computes the number of partitions of n with largest part equal to k , for 1 < k < n < N , in time O (log 2 ( N )) using O ( N 2 /log N ) processors. Parallel logarithmic time algorithms that generate partitions uniformly at random, using these quantities, are also presented.

Document Type: Research Article

Affiliations: 1: Department of Computer Science, Colgate University, Hamilton, New York, 13346 2: Networking Hardware Division, IBM Corporation, Research Triangle Park, North Carolina, 27709

Publication date: April 1, 1996

Related content



Share Content

Access Key

Free Content
Free content
New Content
New content
Open Access Content
Open access content
Subscribed Content
Subscribed content
Free Trial Content
Free trial content
Cookie Policy
Cookie Policy
ingentaconnect website makes use of cookies so as to keep track of data that you have filled in. I am Happy with this Find out more