LA home
  N-Queens 3D

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);
     process the answer

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

n=[  ]
op:[ ]

© L. A.
www #ad:

↑ © L. Allison,   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Thursday, 15-Apr-2021 09:33:42 EDT.

Free: Linux, Ubuntu operating-sys, OpenOffice office-suite, The GIMP ~photoshop, Firefox web-browser, FlashBlock flash on/off.