Partitions of a set

A partition of a set is a collection of disjoint non-empty subsets of the set such that their union is the whole set. We construct a function PartitionSet which returns the set of all the partitions of a given set.

> function PartitionSet(s)
>     if #s le 1 then
>         return {{s}};
>     else
>         x := Rep(s);
>         p := PartitionSet(Exclude(s, x));
>         return {Include(y, {x}) : y in p} 
>           join { {Include(z, x)} join Exclude(y, z) : z in y, y in p };
>     end if;
> end function;
>
> PartitionSet({"a", "b", "c"});     
{
    {
        { c, a },
        { b }
    },
    {
        { b, a },
        { c }
    },
    {
        { c, b, a }
    },
    {
        { c, b },
        { a }
    },
    {
        { c },
        { b },
        { a }
    }
}
>
> time #PartitionSet( {1..8} );
4140
Time: 1.169

Another approach to the problem is to do all the computation in terms of a sequence of partitions, converting the sequence to a set at top-level. The following function PartitionWithSeq behaves like PartitionSet from the user's point of view, but calls another function, partnsq, to do most of the task.

> PartitionWithSeq:=function(set)
>
>     function partnsq(seq) //returns sequence of sets of sets
>         if #seq le 1 then
>             return [{Seqset(seq)}];
>         else
>             x := seq[#seq];
>             p := partnsq(Prune(seq));
>             return [Include(y, {x}) : y in p]
>               cat [ {Include(z, x)} join Exclude(y, z) : z in y, y in p ];
>         end if;
>     end function;
>
>     return Seqset(partnsq(Setseq(set)));
>
> end function;
>
> time #PartitionWithSeq( {1..8} );
4140
Time: 1.280

The execution time of this function is slightly greater than that of the first function.

Next Group: Generation of strings from a grammar Previous Group: Counting