[Home] [prev] [up] [next]     ((src/species.as))

8.8 The Species of Subsets

Definition 8.6. The species of subsets is defined as

℘ [U ] = {S | S ⊆ U } ℘[U] = {S|S ⊆ U }
(14)

(15)
for any finite set U.

As given in [BLL98, Chp. 1.3], the species ℘ can be obtained by the combinatorial equation

℘ = E ⋅E
(16)
where E is the species of sets.

However, looking closer at the definition of multiplication F ⋅G of two species F and G, (cf. (37)) one sees that subsets are needed. Thus we decided to implement the species Subset as a basic species.

Type Constructor

Subset

Usage

s: SetSpecies Integer := set [1,2,3];
subsets: Subset Integer := structures(s);
for subset in subsets repeat stdout << subset << newline;

Description

The species of all subsets.

The structures of this species are all the subsets of the given set. Thus, its isomorphism types are the non-negative numbers less than or equal to the size of the input set.

136⟨dom: Subset 136⟩≡   (55)
Subset(L: LabelType): with {
        ⟨exports: Subset 138⟩
} == add {
        ⟨representation: Subset 137⟩
        import from Rep;
        ⟨implementation: Subset 139b⟩
}

Defines:
Subset, used in chunks 144, 174, 178, 179, 633, and 655.

Uses LabelType 62.

Exports of Subset

CombinatorialSpecies L;

coerce: % -> SetSpecies L Converts a subset into an element of SetSpecies.

complement: % -> SetSpecies L Returns the complement of the subset.

We represent a subset as a set a (encoded by an array) together with a characteristic vector indicating which elements a belong to the subset. Note that we therefore depend on an—albeit arbitrary—ordering of the set.

ToDo ⊲ 23 ⊳
rhx ⊲ 15 ⊳ 15-Mar-2007: The dependence on an order is a good argument to model SetSpecies as we have it and additionally require that LabelType is totally ordered. Note, however, that such a total order on the label type L is only a technical one and should not be confused with the concept of linear species as defined in [BLL98, Chp. 5].
137⟨representation: Subset 137⟩≡   (136)
Rep == Record(char: Integer, set: Array L);

Uses Array 599 and Integer 66.

Let

r: Rep := ...
c: Integer := r.char;
a: Array L := r.set;
n := #a;

then r represents the subset that contains the element ai (i = 0,…,n) if the i-th bit in the binary representation of c is set. The lowest bit has index 0. Note that we keep the order of the elements from the input set.

If r = (c,a) with c = 11 = 8 + 2 + 1 = 010112, a = [1,2,3,4,5], and n = 5 then the corresponding subset-complement pair is

([2,4,5],[1,3]).
(17)
138⟨exports: Subset 138⟩≡   (136)  139a ⊳
CombinatorialSpecies L;

Uses CombinatorialSpecies 71.

For the generation of structures in Times we need the subset as well as its complement. So we provide two functions coerce and complement that return the subset and its complement, respectively.

Export of Subset

coerce: % -> SetSpecies L

Description

Converts a subset into an element of SetSpecies.

139a⟨exports: Subset 138⟩+≡   (136)  ⊲138  140a ⊳
coerce: % -> SetSpecies L;

Uses SetSpecies 117.
139b⟨implementation: Subset 139b⟩≡   (136)  140b ⊳
coerce(x: %): SetSpecies L == {
        u: SetSpecies L := empty;
        c: Z := rep(x).char;
        a: Array L := rep(x).set;
        d: PrimitiveArray L := data a;
        i: I := #a;
        while not zero? i repeat {
                i := prev i;
                if bit?(c, i) then u := cons(d.i, u);
        }
        u;
}

Uses Array 599, I 47, SetSpecies 117, and Z 47.

Export of Subset

complement: % -> SetSpecies L

Description

Returns the complement of the subset.

140a⟨exports: Subset 138⟩+≡   (136)  ⊲139a
complement: % -> SetSpecies L;

Uses SetSpecies 117.
140b⟨implementation: Subset 139b⟩+≡   (136)  ⊲139b  141a ⊳
complement(x: %): SetSpecies L == {
        u: SetSpecies L := empty;
        c: Z := rep(x).char;
        a: Array L := rep(x).set;
        d: PrimitiveArray L := data a;
        i: I := #a;
        while not zero? i repeat {
                i := prev i;
                if not bit?(c, i) then u := cons(d.i, u);
        }
        u;
}

Uses Array 599, I 47, SetSpecies 117, and Z 47.
141a⟨implementation: Subset 139b⟩+≡   (136)  ⊲140b  142a ⊳
structures(s: SetSpecies L): Generator % == generate {
        ⟨n := #s; a: Array L := [u for u in s]; 141b⟩
        for c: Z in 0 .. shift(1, n) - 1 repeat yield per [c, a];
}

Uses Generator 617, SetSpecies 117, and Z 47.

We do not provide a function bracket: Generator L -> % for Array in an Axiom context, and the Aldor version builds an intermediate list. So we fill the array directly.

141b⟨n:= #s; a: Array L := [u for u in s]; 141b⟩≡   (141a 142a)
n: I := #s;
a: Array L := new n;
for u in s for i: I in 0.. repeat a.i := u;

Uses Array 599 and I 47.

Canonical representatives of subsets of a set {1,...,n} are

∅,{1},{1,2} ,{1,2,3},...,{1,2,...,n }.
(18)
The above sequence corresponds to the numbers c = 2i − 1 for 0 ≤ i < n.
142a⟨implementation: Subset 139b⟩+≡   (136)  ⊲141a  142b ⊳
isomorphismTypes(s: SetSpecies L): Generator % == generate {
        ⟨n := #s; a: Array L := [u for u in s]; 141b⟩
        c: Z := 0;
        i: I := 0;
        while i <= n repeat {
                yield per [c, a];
                c := shift(c, 1$I) + 1;
                i := next i;
        }
}

Uses Generator 617, I 47, SetSpecies 117, and Z 47.

The generating series is e2x.

142b⟨implementation: Subset 139b⟩+≡   (136)  ⊲142a  143a ⊳
generatingSeries: ExponentialGeneratingSeries == {
        import from I, Z, Q, DataStream Q;
        s := stream(shift(1$Z, n)/factorialStream(n) for n:I in 0..);
        s :: ExponentialGeneratingSeries;
}

Uses DataStream 386, ExponentialGeneratingSeries 316, I 47, Q 47, and Z 47.

The type generating series is e2x.

143a⟨implementation: Subset 139b⟩+≡   (136)  ⊲142b  143b ⊳
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
        import from Z, DataStream Z;
        stream(z for z: Z in 1..) :: OrdinaryGeneratingSeries;
}

Uses DataStream 386, OrdinaryGeneratingSeries 311, and Z 47.
ToDo ⊲ 24 ⊳
rhx ⊲ 16 ⊳ 15-Mar-2007: Up to the factor 2 in the generator g the code is identical to the cycle index series of SetSpecies. We should reuse code.
The cycle index series Z℘ of the species ℘ of subsets is given by
( ) 2 ∑∞ xn- Z℘(x1,x2,...) = ZE (x1,x2,...) = exp 2⋅ n n=1
(19)
For the workaround see ToDo 10.
143b⟨implementation: Subset 139b⟩+≡   (136)  ⊲143a  144a ⊳
local cis(): CycleIndexSeries == BugWorkaround(
    CycleIndexSeries has with {exponentiate: % -> %}
){
        g: Generator P := generate {
                import from I, Z, Q, V, T, P;
                yield 0$P; -- constant term
                for n:I in 1.. repeat yield [2/(n::Z) , power(n::V, 1)]$P;
        }
        import from DataStream P;
        exponentiate(g :: CycleIndexSeries);
}
cycleIndexSeries: CycleIndexSeries == cis();

Uses BugWorkaround 48, CycleIndexSeries 330, DataStream 386, Generator 617, I 47, Q 47, and Z 47.
144a⟨implementation: Subset 139b⟩+≡   (136)  ⊲143b  144b ⊳
expression: SpeciesExpression == {
        import from String;
        leaf("Subset");
}

Uses SpeciesExpression 430, String 65, and Subset 136.
144b⟨implementation: Subset 139b⟩+≡   (136)  ⊲144a  144c ⊳
(x: %) = (y: %): Boolean == {
        (rep x).char = (rep y).char and
        (rep x).set  = (rep y).set;
}
144c⟨implementation: Subset 139b⟩+≡   (136)  ⊲144b
(tw: TextWriter) << (x: %): TextWriter == {
        import from SetSpecies L;
        tw << "Subset(" << (x :: SetSpecies L) << ", " << complement x << ")";
}

Uses SetSpecies 117 and Subset 136.

[Home] [prev] [up] [next]     ((src/species.as))