## Fast Combinatorial Algorithms in C

#### Siegfried Koepf, 2009-2013

### Content

- 1. Introduction
- 2. Code
- 2.1. Combinations
- 2.1.1.
`k`-combinations without repetition in lexicographic order - 2.1.2.
`k`-combinations without repetition in reverse colexicographic order - 2.1.3.
`k`-combinations with repetition in lexicographic order - 2.1.4.
`k`-combinations with repetition in reverse colexicographic order - 2.2. Partitions
- 2.2.1. Partitions in reverse lexicographic order
- 2.2.2.
`k`-partitions in colexicographic order - 2.2.3.
`k`-compositions in colexicographic order - 2.3.
`n`-tuples - 2.3.1. Variations with repetition in lexicographic order
- 2.3.2. Variations with repetition in colexicographic order
- 2.3.3. Necklaces in lexicographic order
- 2.4. Permutations
- 2.4.1. Permutations with repetition in lexicographic order
- 3. Changelog and bug reports
- 4. Download and license
- 5. Additional reading material

### 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 `a`_{1}...`a _{n}` is obtainable by a three-step procedure:

1) Find the largest

`j`such that

`a`can be increased.

_{j}2) Increase

`a`by the smallest feasible amount.

_{j}3) Find the lexicographically least way to extend the new

`a`

_{1}...

`a`to a complete pattern"(1).

_{j}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 withn = 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 withn = 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 withn = 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 withn = 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 withn = 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 withn = 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 withn = 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 withm = 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 withm = 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 withm = 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 withn = 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`.

They can be downloaded here: `generate.zip`.

### 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: 23.07.2013