Martin Broadhurst

Combinatorial Algorithms

Contents

• Introduction
• Utilities
• Algorithms
  • Power set
  • Power set of each set in the power set
  • Partitions
  • Cartesian product
  • Permutations
  • Combinations
  • Multicombinations
  • Combinations of a multiset
  • Power set of a multiset
  • K-permutations
• Source code

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:

Note that:

• The empty set {} is in the power set
• The set itself is in the power set

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}:

The algorithm then simply needs to produce the arrays shown above. One could just count in binary, but this would not produce the subsets in a sensible order.

To produce the arrays in the above order (by length, then lexicographic), at each step:

1. Find the first 1 with a 0 on its right.
2. Move it right, replacing it with a 0.
3. If there are no 1s to move, add another 1 and put them all at the beginning.

Note the the third step handles the case where there are not yet any 1s.

Implementation

subset.c

Examples

The following program produces the characteristic vectors for the power set of a 3-set:

The following program prints the subsets by using the characteristic vector to retrieve the elements from the parent set:

Power set of each set in the power set

Introduction

This algorithm generates, for each subset in the power set, the power set of that subset.

Algorithm

The algorithm uses a vector containing as many elements as the original set, and counts in base 3 from all zeroes to all twos.

This can then be interpreted for each element as follows:

• 0 - Not present in the subset
• 1 - Present in the subset and in this subset of it
• 2 - Present in the subset, but not this subset of it

The following output shows the correspondence between the vector, the subset, and its subset:

Implementation

subset-subset.c

Example

The following program produces the output shown above:

Partitions

Introduction

A partition of a set is a division of it into disjoint subsets whose union is the set itself.

For example, the partitions of the set {a, b, c, d} are:

Representing partitions

The scheme I am using is as follows: a partition is represented by an array of the same size as the set, and each element in the array is an integer specifying the subset in the partition in which the corresponding element occurs. For example, the array [0, 0, 0, 0] indicates that every element occurs in set 0, the first set, i.e., the partition {{a, b, c, d}}, while the array [0, 1, 2, 3] puts every element in its own set, i.e., the partition {{a}, {b}, {c}, {d}}.

The correspondences for the partitions of a 4-set are as follows:

Partition algorithm

Having established how to represent partitions, the algorithm simply needs to produce the arrays shown above. At each step:

1. Find the rightmost element that is no more than any element to its left.
2. Increment it.
3. Set all of the elements after it to 0.

Implementation

partition.c

Examples

The following program outputs the partition arrays for a 4-set:

The following program prints the partitions by converting the arrays into sets of subsets:

Cartesian product

Introduction

The cartesian product of n sets is the set of ordered n-tuples containing one element from each set.

For example, the cartesian product of the sets {a, b}, {p, q, r} and {w, x, y, z} is:

Cartesian product algorithm

The algorithm uses an array of n integers. Each number in the array represents the index number within the corresponding set of that element.

The algorithm then simply needs to count upwards from n zeroes, with the cardinality of each set determining when a digit rolls over.

For example, these are the correspondences between the array and the n-tuple for the sets in the example:

Implementation

n-tuple.c

Example

The following program produces the output shown above:

Permutations

Introduction

The permutations of a set are the ways of arranging its elements.

For example, there are 24 permutations of a set of 4 elements:

Permutation algorithm

To find the next permutation of an array ar:

1. Find the highest index, i₁ such that ar[i₁] is the first of a pair of elements in ascending order. If there isn't one, the sequence is the highest permutation, so reverse the whole thing to begin again.
2. Find the highest index i₂, such that i₂ > i₁ and ar[i₂] > ar[i₁].
3. Swap ar[i₁] and ar[i₂].
4. The elements from ar[i₁ + 1] to the end are now in descending order (a later permutation), so reverse them.

Implementation

permutation.c

Example

The following program produces the output shown above:

Using elements other than integers

To use elements other than integers, use the array elements as indices into an array containing the real elements.

For example, the following program permutes the set {a, b, c, d}:

Combinations

Introduction

Combinations, or k-combinations, are the unordered sets of k elements chosen from a set of size n.

For example, there are 10 3-combinations of the 5-set {0, 1, 2, 3, 4}:

The set of all combinations 0 ≤ k ≤ n is the power set.

Combinations that can contain duplicates are called multicombinations.

Combinations of a set containing duplicates are combinations of a multiset.

Combinations where order is significant are called k-permutations.

Combination algorithm

This algorithm produces the combinations in lexicographic order, with the elements in each combination strictly increasing in magnitude.

Begin with the combination containing the the numbers from 0 to k - 1, and at each step:

1. Find the rightmost element ar[i] that is less than the maximum value it can have (which is (n - 1) - (k - 1) - i)
2. Increment it
3. Turn the elements after it into a linear sequence continuing from ar[i]

Implementation

combination.c

Example

The following program produces the output shown above:

Using elements other than integers

To generate combinations of elements other than the integers from 0 to n, use the numbers in the array as indices into an array containing the real elements.

For example, the following program generates the 3-combinations of the set {a, b, c, d, e}:

Multicombinations

Introduction

A multicombination is a combination that can contain duplicates (i.e., the combination is a multiset).

Note that the source set does not contain duplicates. For combinations of a set that contains duplicates, see combinations of a multiset.

These are the 3-multicombinations of the 4-set {0, 1, 2, 3}:

Multicombination algorithm

This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.

To find the next multicombination containing k elements from a set containing n elements, begin with the multicombination containing k zeroes, then at each step:

1. Find the rightmost element that is less than n - 1
2. Increment it.
3. Make the elements after it the same.

Implementation

multicombination.c

Example

The following program produces the output shown above:

Combinations of a multiset

Introduction

These are the combinations of k elements chosen from a set that can contain duplicates (a multiset).

For example, given the multiset {0, 1, 1, 2, 2, 2, 3}, the 4-combinations are:

Combinations of a multiset algorithm

This algorithm produces the combinations in lexicographic order, with the elements in each combination in increasing order.

Begin with the first combination, which is the first k elements of the multiset ([0, 1, 1, 2] in the example above), and then at each step:

1. Find the rightmost element that is less than the maximum value it can have (which is the element in the multiset that is the same distance from the right).
2. Replace it with the first multiset element greater than it.
3. Replace the remainder of the combination with the elements that follow the replacement in the multiset.

Implementation

multiset-combination.c

Example

The following program produces the output shown above:

Using elements other than integers

To use elements other than integers, use the numbers in the array as indices into an array that contains the real elements.

For example, the following program prints the combinations of the multiset [a, b, b, c, c, c, d]:

Power set of a multiset

Introduction

The power set of a multiset is the set of all its subsets, which are themselves multisets.

For example, the power set of the multiset [a, b, b, c] consists of the sets:

The set of all subsets of a particular size are combinations of a multiset.

Algorithm

The multiset and its subsets are represented as a vector containing, for each element, the count of its occurrences in the multiset. For example, the multiset [a, b, b, c] is represented as [1, 2, 1]. This is similar to the characteristic vector used for power set, but with counts rather than boolean values.

The correspondences for the subsets are then as follows:

The algorithm can then simply count from [0, 0, 0] to [1, 2, 1], using the values in the source multiset as the upper limit for the value of an element.

Note that this algorithm does not produce the subsets in lexicographic order.

Implementation

multiset-subset.c

Examples

The following program prints the vectors for the subsets of the multiset [a, b, b, c]:

The following program prints the subsets of the multiset [a, b, b, c] by using the vector to retrieve the elements from the parent multiset:

K-permutations

Introduction

The k-permutations of a set are the permutations of the combinations of size k.

There are 24 3-permutations of the 4-set {0, 1, 2, 3}:

K-permutation algorithm

The algorithm simply finds the next permutation of the array. If the array is at the last permutation, the next combination from the set is constructed.

Note that this algorithm does not produce the k-permutations in lexicographic order.

Implementation

k-permutation.c

Example

The following program produces the output shown above:

Using elements other than integers

To use elements other than integers, use the numbers in the array as indices into an array containing the real elements.

For example, the following program prints the 3-permutations of the set {a, b, c, d}:

Source code

The following archives contain all of the source code and examples:

• mbcomb.tar.gz (6 KB, Linux)
• mbcomb.zip (19 KB, Windows)