Partitions |
|
Partitions of a SetA partition of a set, S,
is a collection of disjoint sets,
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 IntegerA 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, The HTML FORM below allows partitions of small integers to be calculated (press the `go' button): © L. A. , School of Computer Science and Software Engineering, Monash University, Australia 3149 |
|
|