 Sample Structures - Maple Programming Help

Home : Support : Online Help : Applications and Example Worksheets : Discrete Mathematics : examples/combstruct_sample_structs

Combinatorial Structures Package - Sample Structures

The combstruct package is used to define, count, and generate combinatorial structures.

A combinatorial class is defined by writing a grammar specification that describes it.  In this way, an extensive collection of different classes may 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.

Given a grammar specification, the system creates a dedicated counting procedure for that structure.  The number of objects of size n are counted in worst-case O(n^2) arithmetic operations.  This bound is independent of the combinatorial class.

In the same way, an object of size n is generated uniformly at random in worst-case O(n log(n)) arithmetic operations.  Again, this bound applies to all structures. O(n log(n)) is the best known bound for many combinatorial classes.

This worksheet explores, through examples, some of the uses of the combstruct package.  A companion worksheet, Introduction to the Combinatorial Structures Package, explains in detail how to write a grammar specification, the predefined structures available in combstruct, and the use of the various functions.

 > with(combstruct):