Partitions

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Algorithms
 glossary
 Recursion
  Linear
  Binary
  Permutations
  Partition
  N-Queens
  N-Queens 3D
  Necklaces
  Self-Ref

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. ,
School of Computer Science and Software Engineering, Monash University, Australia 3149
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Saturday, 30-Mar-2024 01:07:17 AEDT.