download partitions program
download Delphi-7 project
A partition of (integer) number A is a collection of (integer) numbers xi such that: x1+x2+...+xn = A.
Say we want to know in how many ways a rope of 20cm. long may be cut in 4 pieces.
The sequence is not important so we may sort the pieces from small to large.
All pieces are rounded to the centimeter.
Partitions also show up in puzzle solving where the ages of players add up to a fixed amount
and other constraints have to be satisfied.
This publication presents a short Delphi program that systematically generates partitions.
These partitions are listed together with their rank.
Permutations and combinations may be generated directly from their rank.
For partitions this is not possible.
Rank 3 must be generated from rank 2, rank 2 from rank 1.
To generate partitions we have to know
- the sum
(showing the program at work)
The left column lists the rank.
Terms are sorted small to large.
The partition generating algorithmSetting the first partition
All columns except the last one are set to "1".
Then the last column is set to SUM - (TERMS-1).
Finding the next partition after 1,1,1,9
please look at picture below:
The partition terms are in array A[1...maxTERM].
Index variable i increments 1,2,3,4.
Values A,A,A are added together in variable broom that sweeps the terms together.
A must be decreased to 8.
Then the terms A..A have to be reset.
This is only possible if these terms may hold the broom.
A being 8 and knowing terms A..A must be <= 8, room = 8*3 = 24 > broom.
The largest value for A = 2, now broom becomes broom - 2 = 2.
The largest value for A = 1, broom becomes broom -1 = 1.
Finally A is set to broom = 1.
This is the general rule:
then the previous terms A..A[i-1] are reset
SUM=20, TERMS=5, shown is rank 23 and the calculation of rank 24
At i=3, room=4 because A may decrement to 2 so the maximum value of A,A = 2
room = 2*2 = 4.
broom=3 = A + A.
Because room > broom we may decrement A and reset terms A, A.
Constants and variables:
const maxSUM = 50; maxTERM = 20; var A : array[1..maxTERM] of byte; SUM : byte; TERMS : byte;This procedure sets the first partition (0):
procedure partition1; //set 1st partition (#0) var i : byte; begin for i := 1 to TERMS-1 do A[i] := 1; A[TERMS] := SUM - (TERMS-1); end;And this function calculates the next rank:
function nextpartition : boolean; //return false if all done var i,j : byte; broom, room : word; up : boolean; begin i := 1; up := false; broom := A; repeat inc(i); room := (A[i]-1)*(i-1); if room > broom then begin dec(A[i]); inc(broom); j := i-1; while broom > 0 do begin if broom-j >= A[j+1] then A[j] := A[j+1] else A[j] := broom - (j-1); broom := broom - A[j]; dec(j); end;//while up := true; end else broom := broom + A[i]; until up or (i = TERMS); result := up; end;If no new partition can be made the function exits with a false result.
For details please refer to the source code.