Introduction to the Combinatorial Structures Package
The combinatorial structures package, combstruct, is used to define and manipulate combinatorial structures. With combstruct, you can define a combinatorial class of objects; generate uniformly at random, objects belonging to that class; count the number of objects of a given size; and analyze properties of the object. For certain common structures which have been predefined in the system, it is possible to create an iterator which traverses all the objects in the given class, and to list all such objects at once. There are two main portions to combstruct. The facility to define your structures using a grammar and using the predefined structures provided. Note: The predefined structures portion of combstruct provides an extension of the functions in the combinat package involving combinations, permutations, partitions, compositions, and subsets. The combstruct functions do everything these functions do, and more as well as providing a consistent interface in terms of function names and syntax. This worksheet is an introduction to the basics of how to define combstruct grammars and some basic uses. See the companion generating functions page for more details on how to determine equations, series representations and even solve for the generating functions of the objects. Also, there are several worksheets which describe some interesting applications and extensions of combstruct, at the level of additional functionality for attribute analysis, and some of complex examples. The help pages give an overview. In particular, see combstruct, combstruct[specification], and combstruct[structures].
For more examples, see the other combstruct example worksheets Sample Structures, and Generating Functions. For more advanced examples, see Attribute Grammars.
First, load the combstruct package functions.
with(combstruct):
Grammar Specifications
The strength of this system is in the ability to define your combinatorial structures. A combinatorial class is defined by writing a grammar specification that describes it. In this way, an extensive collection of different classes can be defined. For example, the system applies to all regular and context-free grammars, grammars to define binary trees, plane general trees, necklaces, functional graphs, expression trees, etcetera. All grammar specifications can be labeled or unlabeled. Grammar specifications are written using Atom, Epsilon, and the constructors Union, Prod, Set (multi-set: repetition of elements is allowed), Sequence, Cycle, Subst (substitution), and PowerSet (set with no repetitions allowed). Once you have a grammar specification, you can draw one or all objects of a given size, uniformly at random; count the number of objects of that size; and try to solve for their generating functions. First, consider the basic constructors. Union and Prod
For a very simple example, consider binary trees. Define a specification for a binary tree using the constructors for unions and product as follows:
sys := {B = Union(Z, Prod(B,B))};
sys:=B=UnionZ,ProdB,B
A binary tree is either a single leaf, Z, for the tree of size 1, or (the Union gives the 'or') it is made up of two (smaller) binary trees joined together (by Prod) at the root.
You can generate binary trees of size 5 uniformly at random using the function draw.
draw([B, sys], size=5);
ProdProdZ,ProdZ,Z,ProdZ,Z
ProdProdZ,ProdProdZ,Z,Z,Z
You can also generate all trees of a certain size 5.
allstructs([B, sys], size=5);
ProdProdZ,ProdZ,Z,ProdZ,Z,ProdProdZ,ProdProdZ,Z,Z,Z,ProdProdProdZ,Z,ProdZ,Z,Z,ProdProdZ,ProdZ,ProdZ,Z,Z,ProdZ,ProdZ,ProdProdZ,Z,Z,ProdProdZ,Z,ProdZ,ProdZ,Z,ProdProdZ,Z,ProdProdZ,Z,Z,ProdZ,ProdProdProdZ,Z,Z,Z,ProdZ,ProdProdZ,Z,ProdZ,Z,ProdZ,ProdZ,ProdZ,ProdZ,Z,ProdProdProdZ,ProdZ,Z,Z,Z,ProdZ,ProdProdZ,ProdZ,Z,Z,ProdProdProdProdZ,Z,Z,Z,Z,ProdProdProdZ,Z,Z,ProdZ,Z
Labeled and Unlabeled
By default, structures are unlabeled, so atoms are not distinguishable. Any specification can also be treated as labeled. The same specification can be used to generate labeled binary trees.
count([B, sys, labeled], size=5);
1680
draw([B, sys, labeled], size=5);
ProdProdProdZ4,Z2,Z3,ProdZ1,Z5
count([B, sys, unlabeled], size=5);
14
Atom and Epsilon
Z is an atom that is built into the system. Other atoms can be defined in a grammar specification. For example, you can define a necklace that has beads of three different colors.
necklace := {N=Cycle(Union(red,blue,green)),red=Atom,blue=Atom,green=Atom}:
draw([N,necklace,unlabeled], size=10);
Cyclered,blue,blue,red,blue,blue,blue,green,green,blue
All atoms have weight one. The object Epsilon has weight 0. The previous definition of a binary tree did not allow for the empty tree. This new definition does.
tree := {T = Union(Epsilon, B), B=Union(Z, Prod(Z,Z))}:
draw([T, tree, unlabeled], size=0);
Ε
That is not the letter "E", that is how Maple displays a capital Epsilon.
Like atoms, you can give different names to Epsilon. This is particularly useful to tag smaller components of an overall structure. For example, to model series and parallel circuits of resistors, a parallel circuit is made up of two or more resistors in series, and a series circuit is made up of two or more parallel circuits.
circuit :={C=Union(P,S,R), P=Set(Union(S,R),card>=2), S=Set(Union(P,R),card>=2), R=Atom}:
count([C,circuit,labeled], size=5);
472
draw([C,circuit,labeled], size=5);
SetR4,SetR3,R1,R5,R2
Each set contains (sub) circuits made up of one or more resistors. From this result, you cannot know which subcircuits are joined in parallel and which are joined in series because of the symmetry in their definitions. Rewrite the grammar, adding an Epsilon tag to each portion of the specification.
circuit2 :={C=Union(P,S,R), P=Prod(par,Set(Union(S,R),card>=2)), S=Prod(ser,Set(Union(P,R),card>=2)), R=Atom, par=Epsilon,ser=Epsilon}:
count([C,circuit2,labeled],size=5);
draw([C,circuit2,labeled],size=5);
Prodser,SetProdpar,SetR2,Prodser,SetR3,R4,R5,R1
Members of the sets that are associated with the tag "par" via a product are joined together in parallel, and those marked with the tag "ser" are joined together in series. Since Epsilon has weight 0, you have not changed the number of objects of each size.
Set, Cycle, and Sequence
As shown in the above example, you can specify the cardinality of a set (insist that all circuits have at least two resistors). You may also specify the cardinality of cycles and sequences.
count([M, {M=Set(Z, card > 8)}, labeled], size=7);
0
draw([A, {A=Cycle(Z, card=4)},labeled],size=4);
CycleZ1,Z2,Z4,Z3
count([A, {A=Cycle(Z, card=4)},labeled],size=3);
draw([S, {S=Sequence(Set(Z, card>0), card <=10)}, labeled], size=6);
SequenceSetZ1,Z5,SetZ2,Z6,SetZ4,SetZ3
The attempt to draw from an empty set provokes an error.
count([S, {S=Sequence(Z, card <=10)}, labeled], size=13);
draw([S, {S=Sequence(Z, card <=10)}, labeled], size=13);
Error, (in combstruct/drawgrammar) there is no structure of this size
Subst
Subst is a mechanism that allows the substitution of all the atoms of one object by another object. Subst(A,B) means, take a B-object, and for every atom in that object, replace the atom with an A-object. Use Subst to write a recursive definition of 2-3 trees. A 2-3 tree is a tree that has all its leaves at the same level, and every internal vertex has either two or three children. Define the tree by specifying that it is either a single leaf, or it is a 2-3 tree with each of the leaves replaced by an internal vertex with 2 children or an internal vertex with 3 children.
t23 := {T = Union(Z, Subst(Union(Prod(Z,Z), Prod(Z,Z,Z)), T)) }:
draw([T, t23], size=11);
ProdProdProdZ,Z,Z,ProdZ,Z,ProdProdZ,Z,Z,ProdZ,Z,Z
PowerSet
A PowerSet is a set without repetition, as opposed to the Set constructor which allows repetition of elements. Use PowerSet to define integer partitions with distinct parts.
sys := {L = PowerSet(Sequence(Z,card>=1)) },unlabeled;
sys:=L=PowerSetSequenceZ,1≤card,unlabeled
draw([L,sys],size=5);
PowerSetSequenceZ,SequenceZ,Z,Z,Z
seq(count([L,sys],size=i),i=1..10);
1,1,2,2,3,4,5,6,8,10
Manipulating Output
The object returned by draw is a Maple object which can be manipulated with other commands. This is useful to change the result from its very general form to one more suited to the particular problem. For example, generate words of the form C = (a C b) *
sys := { C=Sequence( Prod(a, C, b)), a=Atom, b=Atom}:
draw([C,sys], size=6);
SequenceProda,SequenceProda,Ε,b,Proda,Ε,b,b
In this example, Epsilon means that the empty sequence was chosen. All that is required is a string of a's and b's. The draw command provided more information about the derivation structure than is required. To simplify, do the following.
eval(subs(Prod=( ()->args ), Sequence=( ()->args ), Epsilon=NULL, %));
a,a,b,a,b,b
Predefined Structures
Certain combinatorial structures are common enough that they merit specialized algorithms rather than using the very general methods obtained with grammars. The structures that are predefined in the combstruct system are: Combination (also called Subset) - combinations of elements Permutation - permutations of elements Partition - integer partitions (split into summands, order does not matter) Composition - integer compositions (split into summands, order matters) The functions that understand these structures are draw, count, allstructs, and iterstructs. Like structures defined by a grammar, you can draw and count them.
draw(Combination({a,b,c,d,e,f,g}), size=5);
e,f,g,c,d
count(Partition(95), size=40);
450768
All the functions that manipulate these structures have the same syntax. As in manipulating structures defined by grammars, the first argument to the function is a definition of the structure, and the second is the size. The structure is defined by Structure(structure arguments), where the structure arguments depend on the structure. Thus, Partition and Composition require integers, whereas Combination and Permutation accept lists, sets, or integers (in which case the integer n is treated to mean {1,...,n} for Combination and [1,...,n] for Permutation). Each structure has a default size associated with it, so when no size is specified, the function makes the most natural assumption for the structure. Also, instead of giving an integer as a size, the string 'allsizes' can be specified, meaning that the structure should be chosen from all possible sizes of the object defined. ('allsizes' is the default for all structures except Permutation, where the default is the number of elements in the list to be permuted.)
draw(Combination({a,b,c,d,e,f,g}));
f,g,b,c,d
draw(Permutation(42));
8,17,27,35,9,34,16,28,30,19,41,31,32,6,36,18,20,40,25,7,29,22,39,5,10,1,12,26,15,42,37,4,38,23,13,14,3,24,11,21,33,2
draw(Permutation(16),size='allsizes');
8,15,13,5,3,10,16
draw(Composition(32));
1,1,2,2,1,1,3,1,3,1,1,1,2,1,4,2,2,2,1
The function allstructs is used to generate all the structures of a given size.
allstructs(Combination(4));
,1,1,2,3,4,2,3,4,3,4,1,3,4,4,1,4,2,4,2,3,2,3,1,2,3,1,2,1,3,1,2,4
allstructs(Permutation([a,a,b,c]),size=3);
a,a,b,a,a,c,a,b,a,a,b,c,a,c,a,a,c,b,b,a,a,b,a,c,b,c,a,c,a,a,c,a,b,c,b,a
allstructs(Partition(4));
1,1,1,1,1,1,2,2,2,1,3,4
allstructs(Composition(6));
6,5,1,4,2,3,3,2,4,1,5,4,1,1,3,2,1,2,3,1,1,4,1,2,2,2,1,3,2,3,1,2,2,1,3,1,2,3,1,1,4,2,2,1,1,1,3,1,1,3,1,1,1,2,1,2,1,1,2,2,1,1,1,3,1,1,1,2,2,2,1,1,2,1,2,1,2,1,1,1,3,1,1,1,2,1,1,1,2,1,1,2,1,1,1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,1,1
The function iterstructs creates a mechanism to generate all the structures of a given size, one at a time. The functions nextstruct and finished are used to manipulate the table returned by iterstructs.
it := iterstructs(Combination([apple, orange, banana]), size=2):
while not finished(it) do nextstruct(it) od;
apple,banana
apple,orange
banana,orange
it := iterstructs(Permutation(3), size='allsizes'):
1
2
3
1,2
2,1
1,3
3,1
2,3
3,2
1,2,3
2,1,3
3,1,2
1,3,2
2,3,1
3,2,1
You can add specialized structures into the combstruct system. For details on how to do this, see combstruct[structures].
See Also
Attribute Grammars, combstruct, combstruct[agfeqns], combstruct[allstructs], combstruct[count], combstruct[draw], combstruct[finished], combstruct[iterstructs], combstruct[nextstruct], combstruct[specification], combstruct[structures], Generating Functions, Sample Structures
Return to Index for Example Worksheets
Download Help Document
