Partitions

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);

L
.
A
l
l
i
s
o
n

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

n=[  ]
op:[ ]

© L. A.