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:


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
l
l
i
s
o
n
n=[  ]
op:[ ]

© L. A.
www #ad:

↑ © L. Allison, www.allisons.org/ll/   (or as otherwise indicated).
Created with "vi (Linux)",  charset=iso-8859-1,   fetched Friday, 29-Mar-2024 04:34:35 UTC.

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