Combinatorial Algorithms

By Martin Broadhurst

Contents

Introduction

This is a collection of combinatorial algorithms I've written in C.

Utilities

As well as the algorithms, I have provided some utilities for printing collections. The examples should make their use clear. They are:

void MBprint_array(const unsigned int *ar, size_t len, FILE *fptr);
Print an array of unsigned integers
void MBprint_set(const unsigned int *ar, size_t len, const void **elements, const char *brackets, MBprintfn print, FILE *fptr);
Print a set represented as an array of integer indices by looking them up in an array of values
void MBprint_subset(const unsigned int *ar, size_t len, const void **elements, MBprintfn print, FILE *fptr);
Print a subset represented by a characteristic vector by getting the values from a parent set array
void MBprint_partition(const unsigned int *ar, size_t len, const void **elements, MBprintfn print, FILE *fptr);
Print a partition represented by an array of integers as a set of sets by looking them up in a parent set array of values
void MBprint_multiset_subset(const unsigned int *ar, size_t len, const void **elements, MBprintfn print, FILE *fptr)
Print a subset of a multiset represented by a vector of occurrence counts by getting the values from a parent muliset array
void MBprint_n_tuple(const unsigned int *ar, size_t len, const size_t *sizes, const void ***variables, MBprintfn print, FILE *fptr)
Prints an ordered n-tuple represented by a vector of indices by getting the values from a set of sets

The utilities are in comb-util.c.

Algorithms

Power set

Introduction

The power set is the set of all subsets of a set.

For example, the power set of the set {a, b, c} consists of the sets:

{}
{a}
{b}
{c}
{a, b}
{a, c}
{b, c}
{a, b, c}

Note that:

The set of all subsets of a particular size, or k-subsets, are combinations.

Power set algorithm

A subset can be represented as an array of boolean values of the same size as the set, called a characteristic vector. Each boolean value indicates whether the corresponding element in the set is present or absent in the subset.

This gives following correspondences for the set {a, b, c}:

[0, 0, 0] = {}
[1, 0, 0] = {a}
[0, 1, 0] = {b}
[0, 0, 1] = {c}
[1, 1, 0] = {a, b}
[1, 0, 1] = {a, c}
[0, 1, 1] = {b, c}
[1, 1, 1] = {a, b, c}

The algorithm then simply needs to produce the arrays shown above. Observing how they change, one can derive the following algorithm: