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. Articles by others on the same topic
There are currently no matching articles.