The Combinatorica Project
Sriram V. Pemmaraju
Department of Computer Science, The University of Iowa
Department of Computer Science, State University of New York at Stony Brook
Combinatorica is a package written in 1989 by Steve Skiena for doing
computational discrete mathematics in Mathematica.
It included over 230 functions and has been a Standard AddOn
Steve Skiena described this package in his book
Implementing Discrete Mathematics: Combinatorics and Graph Theory in
Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990.
Along with Steve Skiena I am developing a
"new" Combinatorica package that is expected to be released in the
first half of 2001.
How computational discrete mathematics is done using the new
package will be described in a forthcoming book:
Computational Discrete Mathematics: Combinatorics and Graph Theory in
Cambridge University Press, September 2002
Want the latest Combinatorica package?
Download Version 2.0.0 from here and
the list of known bugs in this version.
(last update: March 5, 2003, size: 341KB)
I am using Combinatorica in
the course "Computational Combinatorics"
For lecture notes and other resources, visit its homepage here.
How is the new Combinatorica different?
The "new" Combinatorica is an almost
complete rewrite of the old package.
The rewrite was done primarily to:
- Significantly speed up most of the functions: This has been
achieved by changing underlying data structures and algorithms,
using code compilation judiciously,
taking advantage of packed arrays in Mathematica 4.0,
and in general paying closer attention to the Mathematica model
Here is an example of the kind of speedup obtained.
- Treat several new topics: These include set partitions, Polya
theory, tree enumeration, Catalan families, planar graphs and embeddings,
and approximation algorithms for NP-hard problems.
Here is an example of a few Polya theory related
- Significantly improve on the graphics: A user can now color
vertices and edges, draw them in different styles, display edge and vertex
weights and labels and in general produce high quality graph drawings.
Here is an example of the kinds of graph
drawings the "new" Combinatorica is
capable of producing.
- Provide a large database of combinatorial objects and interface
Combinatorica with other discrete math packages:
The files provided here are rather large, especially the postscript files.
Ideally, you should download Mathematica notebooks, ignoring the postscript
and pdf versions.
Even those who don't have access to Mathematica can read these notebooks
by downloading MathReader from Wolfram Research.
Here is a demo I presented to Wolfram Research providing an overview of
the ways in which the New Combinatorica is an
improvement over the old: Mathematica notebook,
(Last updated: June 14, 2001.)
Here is the beginning of a Mathematica tutorial for
that I am constructing: Mathematica notebook,
(Last updated: June 14, 2001.)
- Examples, examples, and more examples.
Note: These examples are slightly out of date and the few examples that
don't work can be made to work by a slight modification in the syntax.