Koepf's Editions – Computer Projects – Fast Combinatorial Algorithms in C
German

Fast Combinatorial Algorithms in C

Siegfried Koepf, 2009-2013

1. 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 concept: 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 scheme. However, in some situations it will be modified by enumerating in reverse lexicographic order, in colexicographic order or in reverse colexicographic order.

An exception is the program for generating Permutations with repetitions. Here the function gen_perm_rep_lex_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.

2. 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.

2.1. Combinations

2.1.1. k-combinations without repetition in lexicographic order

added on 26.04.2009
source files:
comb_norep_lex.c
comb_norep_lex_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

2.1.2. k-combinations without repetition in reverse colexicographic order

added on 10.07.2013
source files:
comb_norep_revcolex.c
comb_norep_revcolex_example.c

Example with
n = 5, k = 3
2 3 4
1 3 4
0 3 4
1 2 4
0 2 4
0 1 4
1 2 3
0 2 3
0 1 3
0 1 2

2.1.3. k-combinations with repetition in lexicographic order

added on 26.04.2009
source files:
comb_rep_lex.c
comb_rep_lex_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

2.1.4. k-combinations with repetition in reverse colexicographic order

added on 10.07.2013
source files:
comb_rep_revcolex.c
comb_rep_revcolex_example.c

Example with
n = 3, k = 3
2 2 2
1 2 2
0 2 2
1 1 2
0 1 2
0 0 2
1 1 1
0 1 1
0 0 1
0 0 0

2.2. Partitions

2.2.1. Partitions in reverse lexicographic order

added on 26.04.2009
source files:
part_revlex.c
part_revlex_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

2.2.2. k-partitions in colexicographic order

added on 26.04.2009
source files:
k_part_colex.c
k_part_colex_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

2.2.3. k-compositions in colexicographic order

added on 06.02.2012
source files:
k_comp_colex.c
k_comp_colex_example.c

Example with
n = 7, k = 5
3 1 1 1 1
2 2 1 1 1
1 3 1 1 1
2 1 2 1 1
1 2 2 1 1
1 1 3 1 1
2 1 1 2 1
1 2 1 2 1
1 1 2 2 1
1 1 1 3 1
2 1 1 1 2
1 2 1 1 2
1 1 2 1 2
1 1 1 2 2
1 1 1 1 3

2.3. n-tuples

2.3.1. Variations with repetition in lexicographic order

added on 26.04.2009
source files:
vari_rep_lex.c
vari_rep_lex_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

2.3.2. Variations with repetition in colexicographic order

added on 10.07.2013
source files:
vari_rep_colex.c
vari_rep_colex_example.c

Example with
m = 2, n = 3
0 0 0
1 0 0
0 1 0
1 1 0
0 0 1
1 0 1
0 1 1
1 1 1

2.3.3. Necklaces in lexicographic order

added on 26.04.2009
source files:
neck_lex.c
neck_lex_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

2.4. Permutations

2.4.1. Permutations with repetition in lexicographic order

added on 26.04.2009
source files:
perm_rep_lex.c
perm_rep_lex_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

3. Changelog and bug reports

Bug reports are welcome here. For a history of changes, see the file CHANGELOG.

4. Download and license

The C sources on this site are published under the GNU General Public License version 3, see the file COPYING.
Download

5. Additional reading material

Arndt, Jörg: Matters Computational: ideas, algorithms, source code. 2009. URL: 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: www.math.upenn.edu/~wilf (02.02.2009).

Ruskey, Frank: Combinatorial Generation. Working Version 2003. URL: 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.

Last update: 20.10.2021