Search
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.
Mensa®
Daily Puzzlers
For over 15 years
Mensa Page-A-Day calendars have provided several puzzles a year
for my programming pleasure. Coding "solvers" is most fun,
but many programs also allow user solving, convenient for "fill
in the blanks" type. Below are Amazon links to the
two most recent years.
Mensa®
365 Puzzlers Calendar 2017
Mensa®
365 Puzzlers Calendar 2018
(Hint: If you can
wait, current year calendars are usually on sale in January.)
Contact
Feedback:
Send an
e-mail with your comments about this program (or anything else).
|
| | 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:
-
No two
different subsets of A have the same sum of elements.
-
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.
-
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:
 |
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. |
|
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}). |
|
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! |
| Created: September 13, 2005 |
Modified:
May 11, 2018
|
|
