Fast Combinatorial Algorithms in C
Siegfried Koepf, February 2009
Introduction
This is not an introduction to the functionality or analysis of combinatorial algorithms. This subject has been investigated and discussed in detail by numerous experts. Really excellent technical literature exists on this topic and a small selection of in part freely available books is listed below. The programs published here were also highly inspired by these writings.
The purpose of this site is to provide some combinatorial algorithms as C code. I wrote these programs in recent years in connection with my practical and theoretical work as a composer and they turned out to be extremely fast and useful tools.
These programs are about exhaustive generation of classical combinatorial objects in a well-defined order. They all follow the same paradigm: they generate the desired sequences one after the other and make them available to the calling program for further processing. We start by calling a function
gen_xxx_init(...)
(where xxx represents the abbreviated name of the related combinatorial class). This function examines the passed arguments for some special cases and writes the first instance of the desired patterns to an array. After the evaluation of the return value the function
gen_xxx_next(...)
is called in a loop to iteratively compute lexicographic successors until the list of objects has been entirely enumerated.
"In general, the lexicographic successor of any combinatorial pattern a1...an is obtainable by a three-step procedure:
1) Find the largest j such that aj can be increased.
2) Increase aj by the smallest feasible amount.
3) Find the lexicographically least way to extend the new a1...aj to a complete pattern"(1).
The comments in the source files refer frequently to this paradigm. However, in some situations it will be slightly modified, for example by enumerating in reverse lexicographic order (see Partitions) or in colex order (see k-partitions). Another exception is the program for generating Permutations with repetitions. Here the function gen_perm_rep_init does not initialize the given array. This has to be done in advance by the calling program, at which point the elements must be arranged in increasing order to obtain all possible permutations. By the way, if these elements are also distinct, this algorithm generates all Permutations without repetitions.
Code
All programs are written in ANSI-C. They work iteratively and in-place. Two files are provided for each algorithm: one of them containing the actual combinatorial code and a second one as an example of its usage. Additionally, all programs must include the header file _generate.h. Further information and appropriate references are to be found in the individual C files.
| k-combinations without repetition in lexicographic order | |
| Source files | comb_norep.c comb_norep_example.c |
| Example with n = 5, k = 3 | |
| 0 1 2 | |
| 0 1 3 | |
| 0 1 4 | |
| 0 2 3 | |
| 0 2 4 | |
| 0 3 4 | |
| 1 2 3 | |
| 1 2 4 | |
| 1 3 4 | |
| 2 3 4 | |
| k-combinations with repetition in lexicographic order | |
| Source files | comb_rep.c comb_rep_example.c |
| Example with n = 3, k = 3 | |
| 0 0 0 | |
| 0 0 1 | |
| 0 0 2 | |
| 0 1 1 | |
| 0 1 2 | |
| 0 2 2 | |
| 1 1 1 | |
| 1 1 2 | |
| 1 2 2 | |
| 2 2 2 | |
| Permutations with repetition in lexicographic order | |
| Source files | perm_rep.c perm_rep_example.c |
| Example with n = 4, {1, 2, 2, 3} | |
| 1 2 2 3 | |
| 1 2 3 2 | |
| 1 3 2 2 | |
| 2 1 2 3 | |
| 2 1 3 2 | |
| 2 2 1 3 | |
| 2 2 3 1 | |
| 2 3 1 2 | |
| 2 3 2 1 | |
| 3 1 2 2 | |
| 3 2 1 2 | |
| 3 2 2 1 | |
| Variations with repetition in lexicographic order | |
| Source files | vari_rep.c vari_rep_example.c |
| Example with m = 2, n = 3 | |
| 0 0 0 | |
| 0 0 1 | |
| 0 1 0 | |
| 0 1 1 | |
| 1 0 0 | |
| 1 0 1 | |
| 1 1 0 | |
| 1 1 1 | |
| Necklaces in lexicographic order | |
| Source files | neck.c neck_example.c |
| Example with m = 2, n = 6 | |
| 0 0 0 0 0 0 | |
| 0 0 0 0 0 1 | |
| 0 0 0 0 1 1 | |
| 0 0 0 1 0 1 | |
| 0 0 0 1 1 1 | |
| 0 0 1 0 0 1 | |
| 0 0 1 0 1 1 | |
| 0 0 1 1 0 1 | |
| 0 0 1 1 1 1 | |
| 0 1 0 1 0 1 | |
| 0 1 0 1 1 1 | |
| 0 1 1 0 1 1 | |
| 0 1 1 1 1 1 | |
| 1 1 1 1 1 1 | |
| Partitions in reverse lexicographic order | |
| Source files | part.c part_example.c |
| Example with n = 6 | |
| 6 | |
| 5 1 | |
| 4 2 | |
| 4 1 1 | |
| 3 3 | |
| 3 2 1 | |
| 3 1 1 1 | |
| 2 2 2 | |
| 2 2 1 1 | |
| 2 1 1 1 1 | |
| 1 1 1 1 1 1 | |
| k-partitions in colex order | |
| Source files | k_part.c k_part_example.c |
| Example with n = 10, k = 4 | |
| 7 1 1 1 | |
| 6 2 1 1 | |
| 5 3 1 1 | |
| 4 4 1 1 | |
| 5 2 2 1 | |
| 4 3 2 1 | |
| 3 3 3 1 | |
| 4 2 2 2 | |
| 3 3 2 2 | |
Bugs
Bug reports are welcome here.
Download und license
The C sources on this site are published under the GNU General Public License version 3, see the file COPYING.
They can be downloaded here: generate.zip.
Additional reading material
Arndt, Jörg: Matters Computational: ideas, algorithms, source code. 2009. URL: http://www.jjj.de/fxt (26.04.2009).
Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 2. Generating All Tuples and Permutations. Upper Saddle River, NJ 2005.
Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 3. Generating All Combinations and Partitions. Upper Saddle River, NJ 2005.
Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 4. History of Combinatorial Generation. Upper Saddle River, NJ 2006.
Nijenhuis Albert/Wilf, Herbert: Combinatorial Algorithms. New York 1978. URL: http://www.math.upenn.edu/~wilf (02.02.2009).
Ruskey, Frank: Combinatorial Generation. Working Version 2003. URL: http://www.1stworks.com/ref/RuskeyCombGen.pdf (02.02.2009).
(1) Knuth, Donald E.: The Art of Computer Programming, Vol. 4: Fascicle 2. Generating All Tuples and Permutations. Upper Saddle River, NJ 2005, 40.
Copyright (c) 2009 by Siegfried Koepf
(Last update: 22.08.2009)