|
|
Partitions of a Set
A partition of a set, S,
is a collection of disjoint sets,
S1, S2, ,...,
such that
S=S1 union S2 union ...
Kruskal's
minimum spanning tree
algorithm uses a partition of the vertices of a graph
during its intermediate stages
to represent a spanning-forest of the graph.
Partitions of an Integer
A partition of an integer, n,
is a set of positive integers, n1, ..., nm
that add up to n.
(The partitions of an integer n are related to
the partitions of a set of size n.)
The partitions of n can be enumerated by a simple recursive routine:
function partition(n, limit, answer)
{ var i;
if(n > 0)
for(i = min(n, limit); i > 0; i --)
partition(n-i, i, answer now including i);
else
process the answer
}//partition
//initial call:
partition(n, n, initial empty answer);
The exact form of the "answer"
depends on what you want to do with a partition,
but it represents it in some way,
e.g. as an array of integers.
The extra parameter, "limit", ensures that each partition is in
non-increasing order,
e.g. 3+1+1, 1+3+1 and 1+1+3 are all considered to be equivalent
and the algorithm only creates the first of these.
The HTML FORM below allows partitions of small integers
to be calculated (press the `go' button):
© L. A.
|
|