Partitions |
|
Partitions of a SetA partition of a set, S,
is a collection of disjoint sets,
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 IntegerA 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,
The HTML FORM below allows partitions of small integers to be calculated (press the `go' button): © L. A. , School of Computer Science and Software Engineering, Monash University, Australia 3149 |
|
|