[Object Server] [Information Index] [Generation Index] [COS homepage]

[Steinhaus-Johnson-Trotter Weave]

The (Combinatorial) Object Server

Thank you for visiting the combinatorial object server, otherwise known as COS. We hope that you will find it informative and useful.

What is it?

The idea is that you specify a type of combinatorial object, together with specific parameter values, and COS will return to you a list of all such objects. COS can generate permutations, combinations, various types of trees, unlabelled graphs, linear extensions of posets, pentomino puzzle solutions, numerical partitions, and a host of other combinatorial objects. In some instances you may specify the order in which the objects are generated (such as lexicographic or a Gray code order). Almost always the output may be presented in a variety of formats which you may specify. These different formats include well-known correspondences and representations of the objects. For example, permutations may be ouput in one-line notation, in cycle notation, or as a pair of Standard Young Tableau under the Schensted correspondence.

Who is it intended for?

We hope that a great variety of people will use COS. It is meant to be used by researchers and educators who wish to easily produce list of combinatorial objects. The elementary objects such as permutations, combinations, and subsets are well-known and studied in the elementary and secondary schools. In fact, there's another version, called The Amazing Mathematical Object Factory, and directed to K12 students and educators, that used to run on Canada's "Schoolnet" before they broke it (the previous link is now to the local version) -- please give it a try if you're looking for something simpler and less comprehensive than COS. On COS, there are some recreational items, such as pentomino puzzle solutions which can be understood by anyone. And then there's more complicated objects such as graphical partitions, linear extensions of posets, primitive polynomials, and unlabelled graphs which will be of interest to university students and scientific/mathematical researchers.

How does it work?

COS does not store any tables of the lists that it produces. Each list is produced by a program on-the-fly. Most of the programs use a recursive backtracking, and some are available for downloading.

What if I want millions of objects?

You may be wondering: ``Are you really going to send me all 2,432,902,008,176,640,000 permutations of 1,2,...,20 if I ask for them?'' Of course not! We now limit your output to 200 objects, and even less for some objects. To get more objects send us e-mail, or download the programs (if available), or consult the references and write your own program.

Caveats

We've made considerable effort to ensure that the output of each program is correct, but we make no guarantees.

We are always curious about who is using COS. Please send us a little note if you find COS useful in your work, if you have suggestions, or if you find something not working quite right.

Sounds Good! Let's try it.

To proceed further you may either generate some objects or access the information pages.

[Generate] This icon, which appears at the top and bottom of each page, takes you to a list of pages which broadly classifies the objects. Select the appropriate classification for the type of object you wish to generate.
[Info] This icon, which appears at the top and bottom of each page, takes you to a list of information pages about various classes of combinatorial objects.
[COS] This icon, which appears at the top and bottom of each page, returns you to this page.

[--]

About the Information Pages

With each type of object is an associated information page. This page provides explanation of the object, the COS options, and the algorithms used to generate the object. Where relevant we also give the number of objects of that type for small parameter values along with the corresponding number in Sloane and Plouffe's The Encyclopedia of Integer Sequences (Academic Press, 1995) or in Sloane's On-Line Encyclopedia of Integer Sequences. For some of the objects programs in Pascal and/or C may be downloaded from the information page.

About the Generation Pages

Each generation page starts with a table asking What Type? where you specify the type of object and possibly the ordering. Next comes a table called Input where you specify the values of the input parameters. A final table called Output is where you specify the form of the output; i.e., the representations of the combinatorial objects that are to be used on output. Exactly one "What Type" option and at least one "Output" option must be specified. Every object (with the exception of pentominoes with custom shape) requires an input parameter named n. Some, such as combinations, require at least one other parameter. Required extra parameters are mentioned under "What Type". Sometimes parameters are optional and these are indicated in smaller font by a comment enclosed in square brackets.

Additional Icon Explanation:

[Generate] Clicking on this icon, which appears on every information page, takes you to the corresponding generation page.
[Info] Clicking on this icon, which appears on every generation page and on every output page, takes you to the corresponding information page.

Don't you hate it when a link takes you a page that contains nothing except a message saying it's under construction! Lots of our pages are under construction, and we expect that we will always have pages under construction. However, you are warned of the state of all links and various options before you use them by one of the following icons.

Icon Meaning
  [IMG = Green Check]   Works great!
  [Under_Construction]   Partially functional, but not all options implemented. Don't be deterred; most of it works well.
  [img Red-x]   Don't waste your time.

Most of the algorithms used are very fast and have the CAT property. This means that the total amount of computation, divided by the number of objects is bounded by a constant; i.e., only a constant amount of computation is done per object, in an amortized sense. Programs with this property have the following icon next to them.

[CAT_ICON] = CAT (Constant Amortized Time) algorithm.

[HOT_ICON] = CAT algorithm not previously published for this object.

[Acknowledgements]


[Information Index] [Generation Index] [COS homepage]

Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
There have been 59360 visitors to this page since May 16, 2000 .
(These are hits to this page only; in total there have been 2988355 hits on the pages of COS since May 16, 2000.)
(Previously, there were over 230,000 hits on the pages of COS.)
It was last updated Monday, 23-May-2011 12:56:55 PDT.
©Frank Ruskey, 1995-2002.





[UVic]

Valid HTML 3.2!

The small print: This is an experimental prototype. Much work will be required to bring it to full functionality. The 200 object limit is for testing purposes, eventually it will be increased. If you like what you see so far, please send us some encouragement. This page and its successors are designed to be viewed with Netscape (Mozilla) [You are using CCBot/2.0 (http://commoncrawl.org/faq/)]. On viewers that don't support tables and subscripts it won't look so good. Here are some acknowledgements, awards, and a list of links to our pages.