Integer Partition Test

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

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

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 Pk(N),  represents the number of partitions of N that contain K elements.  Clearly P(N)=sum(Pk(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:

  1. No  two different subsets of A have the same sum of elements.

  2. For any two subsets, B & C,  if B has more elements than C then the sum of the elements of B is greater than the sum of the elements of C.

  3. A is set which meets the above conditions and has the smallest total sum of elements. "  

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:

bullet

The maximum integer which can be partitioned has been extended to 375.  The number of partitions for this number is over 1018, approaching the maximum number which can be expressed in  64-bit integer format.

bullet

The program will now count and list partitions with a specified maximum value as well as a specified number of parts.  The number of partitions for either of these values for a given integer, K, will be the same.  For example, for N=12 and K=9 there are 3 partitions of 12 which have maximum value 9 ({9.3},{9,2,1}, and {9,1,1}).  There are also 3 partitions of 12 with 9 parts ({4,1,1,1,1,1,1,1,1}, (3,2,1,1,1,1,1,1,1}. and {2,2,2,1,1,1,1,1,1}).  

bullet

The option to compute ranks (positions in the standard form list of all partitions) has also been added.  For example, the 100 millionth (100,000,000) partition of the integer 100 is {20,14,8,8,6,5,5,4,4,3,3,3,3,3,2,1,1,1,1,1,1,1,1,1}.    This calculation takes about 30 seconds on my Dell laptop, but the time is only indirectly related to the rank being calculated.  The 190 millionth is found in less than a second!  

 

bullet

Download executable program
Download source code (Requires library unit DFFLibV14 or later to recompile)

bullet

Download current DFF Library Source   (DFFLibV15 )

 

bulletDownload Lazarus Source
bulletDownload current DFF Lazarus Library Source(DFFLazLib01)

 

 

 


Created: September 13, 2005 

Modified: February 18, 2016

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.