Affordable Access

Publisher Website

Parallel Algorithms for Counting and Randomly Generating Integer Partitions

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
34
Issue
1
Identifiers
DOI: 10.1006/jpdc.1996.0043
Disciplines
  • Computer Science

Abstract

Abstract 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 nwith 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.

There are no comments yet on this publication. Be the first to share your thoughts.