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
Department of Computer Science, Colgate University, Hamilton, New York, 13346 2:
Networking Hardware Division, IBM Corporation, Research Triangle Park, North Carolina, 27709