Combinatorial Problems

In this section, we consider several classic algorithmic problems of a purely combinatorial nature. These include sorting and permutation generation, both of which were among the first nonnumerical problems arising on electronic computers. Sorting, searching, and selection can all be classified in terms of operations on a partial order of keys. Sorting can be viewed as identifying or imposing the total order on the keys, while searching and selection involve identifying specific keys based on their position in the total order.      

The rest of this section deals with other combinatorial objects, such as permutations, partitions, subsets, calendars, and schedules.    We are particularly interested in algorithms that rank and unrank combinatorial objects, i.e. that map each distinct object to and from a unique integer. Once we have rank and unrank operations, many other tasks become simple, such as generating random objects (pick a random number and unrank) or listing all objects in order (iterate from 1 to n and unrank).

We conclude with the problem of generating graphs. Graph algorithms are more fully presented in subsequent sections.

Books on general combinatorial algorithms, in this restricted sense, include:

• Nijenhuis and Wilf [NW78] - This book specializes in algorithms for constructing basic combinatorial objects such as permutations, subsets, and partitions. Such algorithms are often very short but hard to locate and usually are surprisingly subtle. Fortran programs for all of the algorithms are provided, as well as a discussion of the theory behind each of them. See Section for details.
• Ruskey [Rus97] - On its completion, this manuscript in preparation will become the standard reference on generating combinatorial objects. A preview is available via the WWW at http://www-csc.uvic.ca/home/fruskey/cgi-bin/html/main.html .
• Knuth [Knu73a, Knu73b] - The standard reference on searching and sorting, with significant material on combinatorial objects such as permutations.
• Reingold, Nievergelt, Deo [RND77] - A comprehensive algorithms text with a particularly thorough treatment of combinatorial generation and search.
• Stanton and White [SW86] - An undergraduate combinatorics text with algorithms for generating permutations, subsets, and set partitions. It contains relevant programs in Pascal.
• Skiena [Ski90] - This description of Combinatorica, a library 230 Mathematica functions for generating combinatorial objects and graph theory (see Section ) provides a distinctive view of how different algorithms can fit together.   Its author is uniquely qualified to write a manual on algorithm design.

• Sorting
• Searching
• Median and Selection
• Generating Permutations
• Generating Subsets
• Generating Partitions
• Generating Graphs
• Calendrical Calculations
• Job Scheduling
• Satisfiability