Separate integer partitions according to whether they contain a part equal to . Removing one such part is a bijection to partitions of whose parts are at most . The alternatives are disjoint, givingUse , because the empty integer partition is counted once, and for , with for . This Oberon implementation avoids negative recursive arguments:The precondition is . Each recursive call reduces , proving algorithm termination. Every positive part of a partition of is at most , so the required one-argument count is . Counts require a sufficiently wide integer representation.
PROCEDURE P(i, n: INTEGER): INTEGER;
VAR answer: INTEGER;
BEGIN
IF n = 0 THEN answer := 1
ELSIF i = 0 THEN answer := 0
ELSIF i > n THEN answer := P(i-1, n)
ELSE answer := P(i-1, n) + P(i, n-i)
END;
RETURN answer
END P;
PROCEDURE Partitions(n: INTEGER): INTEGER;
BEGIN
RETURN P(n, n)
END Partitions;For partitions into distinct parts, using a part prevents using it again. Hencewhen , with , for , and for . When , use . Thus change the second call in the final branch of
P to D(i-1, n-i) and rename all calls to D. The same split into two disjoint classes proves correctness; its second class removes its unique largest allowed part. The answer is , giving , from and .Write parts in nonincreasing order. The array The recursion invariant is that
part stores the current prefix, and Emit(i,r,len) completes it using parts at most with remaining sum . With Out as the Oberon output module:VAR part: ARRAY MaxParts OF INTEGER;
PROCEDURE Emit(i, r, len: INTEGER);
VAR j: INTEGER;
BEGIN
IF r = 0 THEN
j := 0;
WHILE j < len DO
IF j > 0 THEN Out.Char("+") END;
Out.Int(part[j], 0); j := j+1
END;
Out.Ln
ELSIF i > 0 THEN
IF i <= r THEN
part[len] := i;
Emit(i, r-i, len+1)
END;
Emit(i-1, r, len)
END
END Emit;
PROCEDURE PrintPartitions(n: INTEGER);
BEGIN
Emit(n, n, 0)
END PrintPartitions;part[0..len) is nonincreasing, has sum , and every further part must be at most and at most the last existing part. The first branch includes the next part ; the second excludes it. These alternatives partition all completions, so each integer partition is printed exactly once. A recursive call reduces ; the printing loop's loop invariant is that the first entries have been printed with exactly the necessary separators.For , no partition has more than parts, and the all-ones partition has exactly . Thus the fixed array requires to handle every partition. When a write occurs, and therefore
len < n, so this bound prevents an out-of-range write. Zero prints one empty line, representing the empty integer partition. Available call stack space imposes a further practical limit.Use dynamic programming in increasing order of the maximum permitted part and then of the remaining sum. Let Require . The outer loop invariant says all rows below equal . The inner loop invariant additionally says entries before column in the current row are correct. Its dependencies are the previous row and the earlier column , so no future entry is read. Each state is evaluated once, giving arithmetic operations and stored counts. A memoization table around part (a)'s recursion is another valid way to share states; its entries need a separate “computed” flag because zero is a legitimate answer. Growing count sizes affect bit complexity and can cause integer overflow in a fixed-width
Count be a sufficiently wide integer type and let table have dimensions (MaxN+1) by (MaxN+1):PROCEDURE CountPartitions(n: INTEGER): Count;
VAR i, j: INTEGER;
table: ARRAY MaxN+1, MaxN+1 OF Count;
BEGIN
table[0,0] := 1; j := 1;
WHILE j <= n DO table[0,j] := 0; j := j+1 END;
i := 1;
WHILE i <= n DO
table[i,0] := 1; j := 1;
WHILE j <= n DO
table[i,j] := table[i-1,j];
IF j >= i THEN
table[i,j] := table[i,j] + table[i,j-i]
END;
j := j+1
END;
i := i+1
END;
RETURN table[n,n]
END CountPartitions;Count. Articles by others on the same topic
There are currently no matching articles.