### Partitions

 LA home Computing Algorithms  glossary  Recursion   Linear   Binary   Permutations   Partition   N-Queens   N-Queens 3D   Necklaces   Subgraphs   Brackets   Self-Ref   Partition

#### 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:

```
{ var i;
if(n > 0)
for(i = min(n, limit); i > 0; i --)
partition(n-i, i, answer now including i);
else
}//partition

//initial call:

```
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.Allison
n=[  ]
op:[ ]