[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]

 Most positive integers can be written as the sum of positive integers in several ways. The elements or "parts" of such a sum for an integer n are called a partition of N. Partitions of N can contain as few as a single part {N}, or as many as N parts {1,1,1,.....1}. The normal representation of a partition is as a set of integers which sum to N, without the "+" signs. For example 5 may be partitioned in 7 ways. {5}, {4,1}, {3,2}, {3,1,1}, {2,2,1}, {2,,1,1,1}, {1,1,1,1,1}. Note that the order on the elements of a partition are not significant  they are typically written in colexicographical (reverse dictionary) order, also called standard form (SF). There are two common forms of the function which returns the number of partitions for a given integer: P(N) represents the total number of partitions of N. The other, P(N,k) or P_{k}(N), represents the number of partitions of N that contain K elements. Clearly P(N)=sum(P_{k}(N), k=1 to N). The program available here can generate all partitions or those of a specified size for numbers from 1 to 100. Actually, for P(N) grows quite rapidly, P(100)= exceeds 190 million, so it is not feasible to list partitions for large numbers. The program will stop computing after a specified number up to 1,000 are displayed. I would like to be able to display the partition of a particular rank, say the one millionth partition of 100, but haven't quite figured out how to do it yet. This page was motivated to help solve problem #103 in the Project Euler set of programming challenges: "Find the set, A, of 7 positive integers with the following characteristics:
A challenge indeed! Addendum February 17, 2013: I recently had a project that required using the TIntPartition class and I decided to update it, consolidating several versions floating around DFF into a common UIntegerPartition unit in out library section and include it in the DFFLibV14 library zip file of common library units. Program IntegerPartitionTest Version 2, included here has adds several features to the original test program:

[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 20002017, Gary Darby All rights reserved. 