Definition 8.7. A set partition of a set X is an collection X ⊂P(X) of subsets of X such that X = ⋃ X and Y ∩ Z = ∅ for any Y,Z ∈X with Y Z. X is called a set partition into m parts if cardX = m.
As given in [BLL98, Chp. 1.4], set partitions Par can be obtained by the combinatorial equation
(20) |
However, looking closer at the definition of composition F ∘ G of two species F and G, (cf. (45)) one sees that set partitions are needed. Thus we decided to implement the species Partition as a basic species.
Description
Species of Partitions.
The structures of this species are set partitions. Its isomorphism types are the integer partitions.
Exports of Partition
coerce: % -> Array List L Coerces internal representation to an array of lists.
coerce: % -> SetSpecies SetSpecies L Coerces internal representation to a set of sets.
restrictedGrowthArrays: MachineInteger -> Generator PrimitiveArray MachineInteger Generates restricted growth arrays of a given size.
Clearly, we want set partitions to be a combinatorial species.
We have decided for an array of lists as the representation since it was easier to implement the isomorphism between restricted growth functions and set partitions using an array than a list.
Export of Partition
coerce: % -> Array List L
Description
Coerces internal representation to an array of lists.
Export of Partition
coerce: % -> SetSpecies SetSpecies L
Description
Coerces internal representation to a set of sets.
In order to generate set partitions it is easier to generate restricted growth functions and then use an easy bijection to get the actual set partition.
Definition 8.8. [KS98] A restricted growth function of length n > 0 is a function
f(0) | = 0 | (21) |
f(i) | ≤ 1 + max, if 1 ≤ i < n. | (22) |
The bijection σ which maps restricted growth functions of length n to set partitions of X = is given below.
Let f be a restricted growth function of length n and
(23) |
In order to describe the inverse of σ, we may assume that in a partition X = of the set X the inequalities
(24) |
Export of Partition
restrictedGrowthArrays: MachineInteger -> Generator PrimitiveArray MachineInteger
Usage
macro I == MachineInteger;
setPartitions(n: I): Generator Array List Integer == generate {
zero? n => break;
for a in restrictedGrowthArrays n repeat {
m := a.0;
r: Array List Integer := new(next m, empty);
for i in prev n .. 1 by -1 repeat {
j := a.i;
r.j := cons(i, r.j);
}
r.0 := cons(0, r.0);
yield r;
}
}
for sp in setPartitions 4 repeat stdout << sp << newline;
Parameters
A positive number that gives the length of the restricted growth array.
Description
Generates restricted growth arrays of a given size.
A restricted growth array is not a commonly know in the literature and only used here to efficiently use the array representation of a restricted growth function.
A restricted growth array is identical to a restricted growth function except for the zeroth entry. A restricted growth array of length n > 0 is an array a of non-negative integers such that
a0 | = 1 + max | (25) |
ai | ≤ 1 + max, if 1 ≤ i < n. | (26) |
The call g:=restrictedGrowthArrays(n) returns a generator that generates all restricted growth arrays of size n in lexicographical order starting with [1,0,…,0] and finishing [n,1,2,…,n − 1].
Remarks
For efficiency reasons, the arrays given by the generator might be reused internally, therefore the information should be copied before the generator is stepped again.
Internally it uses an auxiliary array m whose entries are defined in the following way
(27) |
ai | ≤ mi, if 1 ≤ i < n. | (28) |
The function restrictedGrowthArrays starts with initializing
a | = [1,0,…,0] | m | = [0,1,…,1]. |
Note m0 = 0 is never changed after initialization, so that m0a0 > 0 ensures the termination of the of the loop at i = 0.
We have increased to a new “digit” ai and thus must start, behind it with 0 values.
The maximum value that the new digits can take is either mi if ai is still smaller than this value or it is 1 + ai.
Generating set partitions is easy via the correspondence (23) if a restricted growth array is known. We only have to take care that our elements of the input list s are of type L. Thus we use the index of the input list as a correspondence to the restricted growth array. Basically (with the notation below), (23) turns into
In the following we want to preserve the order of the elements in the given list s also in the resulting sets of the partition. For that reason, we first reverse the list s. At the same time we determine the length n of the list.
Note that we must treat the empty (input) list in a special way. There exists exactly one partition of the empty set, namely ∅.
An isomorphism type of a set partition of a set of cardinality n is, basically, the same as an integer partition of n. The (multi-)set of cardinalities of the sets in the set partition is an integer partition.
The implementation is, in fact, very similar to the implementation of integerPartitions, but here we carry the labels along so that each label is used exactly once.
The following functions returns all isomorphism types of partitions of n into parts of size that is not bigger than bound. The last argument len is a counter the increases with every recursive call of the function. It encodes the number of parts of the partition.
See [KS98, Chp. 3.2].
The number of set partitions is given by the Bell number defined as
(29) (30) |
Since we encode the Bell numbers in an exponential generating series, we have to multiply by i! in the code below and finally divide by n!.
To calculate the number of integer partitions of n, we use the O() recurrence from [AS72, p. 825]:
(31) |
(3k2 + k) | = (3k2 − k) + k, | (32) |
(3(k + 1)2 − (k + 1)) | = (3k2 + k) + 2k + 1. | (33) |
According to [BLL98, Chp. 1.4] we have
(34) |
It is necessary to explicitly define a local function divideBy, since otherwise, all series are multiplied with the same factor. For a demonstration of the bug see BUG 5.