Martin Broadhurst

Combinatorial Algorithms

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. The simplest way to do this is to just count in binary.

Implementation

subset.c

Examples

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

#include <stdio.h>

#include <subset.h>
#include <comb-util.h>

int main(void)
{
    unsigned int ar[] = {0, 0, 0};
    const unsigned int n = sizeof(ar) / sizeof(unsigned int);

    do {
        MBprint_array(ar, n, stdout);
        putchar('\n');
    } while (MBnext_subset(ar, n));

    return 0;
}

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

#include <stdio.h>

#include <subset.h>
#include <comb-util.h>

int main(void)
{
    unsigned int ar[] = {0, 0, 0};
    char *elements[] = {"a", "b", "c"};
    const unsigned int n = sizeof(ar) / sizeof(unsigned int);

    do {
        MBprint_subset(ar, n, (void*)elements, (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_subset(ar, n));

    return 0;
}

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:

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

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

Implementation

subset-subset.c

Example

The following program produces the output shown above:

#include <stdio.h>

#include <subset-subset.h>
#include <comb-util.h>

int main(void)
{
    unsigned int ar[] = {0, 0, 1};
    const char *variables[] = {"a", "b", "c"};
    const size_t len = sizeof(ar) / sizeof(unsigned int);

    do {
        MBprint_array(ar, len, stdout);
        fputs(" = ", stdout);
        MBprint_subset_subset(ar, len, (void*)variables, (MBprintfn)puts, stdout);
        putchar('\n');
    } while (MBnext_subset_subset(ar, len));

    return 0;
}

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:

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

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:

[0, 0, 0, 0] = {{a, b, c, d}}
[0, 0, 0, 1] = {{a, b, c}, {d}}
[0, 0, 1, 0] = {{a, b, d}, {c}}
[0, 0, 1, 1] = {{a, b}, {c, d}}
[0, 0, 1, 2] = {{a, b}, {c}, {d}}
[0, 1, 0, 0] = {{a, c, d}, {b}}
[0, 1, 0, 1] = {{a, c}, {b, d}}
[0, 1, 0, 2] = {{a, c}, {b}, {d}}
[0, 1, 1, 0] = {{a, d}, {b, c}}
[0, 1, 1, 1] = {{a}, {b, c, d}}
[0, 1, 1, 2] = {{a}, {b, c}, {d}}
[0, 1, 2, 0] = {{a, d}, {b}, {c}}
[0, 1, 2, 1] = {{a}, {b, d}, {c}}
[0, 1, 2, 2] = {{a}, {b}, {c, d}}
[0, 1, 2, 3] = {{a}, {b}, {c}, {d}}

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:

#include <stdio.h>

#include <partition.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 0, 0, 0};
    const unsigned int len = sizeof(numbers) / sizeof(unsigned int);

    do {
        MBprint_array(numbers, len, stdout);
        putchar('\n');
    } while (MBnext_partition(numbers, len));

    return 0;
}

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

#include <stdio.h>

#include <partition.h>
#include <comb-util.h>

int main(void)
{
    unsigned int ar[] = {0, 0, 0};
    char *elements[] = {"a", "b", "c"};
    const unsigned int n = sizeof(ar) / sizeof(unsigned int);

    do {
        MBprint_partition(ar, n, (void*)elements, (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_partition(ar, n));

    return 0;
}

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:

[a, p, w]
[a, p, x]
[a, p, y]
[a, p, z]
[a, q, w]
[a, q, x]
[a, q, y]
[a, q, z]
[a, r, w]
[a, r, x]
[a, r, y]
[a, r, z]
[b, p, w]
[b, p, x]
[b, p, y]
[b, p, z]
[b, q, w]
[b, q, x]
[b, q, y]
[b, q, z]
[b, r, w]
[b, r, x]
[b, r, y]
[b, r, z]

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:

[0, 0, 0] = [a, p, w]
[0, 0, 1] = [a, p, x]
[0, 0, 2] = [a, p, y]
[0, 0, 3] = [a, p, z]
[0, 1, 0] = [a, q, w]
[0, 1, 1] = [a, q, x]
[0, 1, 2] = [a, q, y]
[0, 1, 3] = [a, q, z]
[0, 2, 0] = [a, r, w]
[0, 2, 1] = [a, r, x]
[0, 2, 2] = [a, r, y]
[0, 2, 3] = [a, r, z]
[1, 0, 0] = [b, p, w]
[1, 0, 1] = [b, p, x]
[1, 0, 2] = [b, p, y]
[1, 0, 3] = [b, p, z]
[1, 1, 0] = [b, q, w]
[1, 1, 1] = [b, q, x]
[1, 1, 2] = [b, q, y]
[1, 1, 3] = [b, q, z]
[1, 2, 0] = [b, r, w]
[1, 2, 1] = [b, r, x]
[1, 2, 2] = [b, r, y]
[1, 2, 3] = [b, r, z]

Implementation

n-tuple.c

Example

The following program produces the output shown above:

#include <stdio.h>

#include <n-tuple.h>
#include <comb-util.h>

int main(void)
{
    unsigned int ar[] = {0, 0, 0};
    const size_t len = sizeof(ar) / sizeof(unsigned int);
    char *set0[] = {"a", "b"};
    char *set1[] = {"p", "q", "r"};
    char *set2[] = {"w", "x", "y", "z"};
    char **elements[] = {set0, set1, set2};
    size_t sizes[] = {sizeof(set0) / sizeof(char*),
            sizeof(set1) / sizeof(char*),
            sizeof(set2) / sizeof(char*)};
    do {
        MBprint_array(ar, len, stdout);
        fputs(" = ", stdout);
        MBprint_n_tuple(ar, len, sizes, (void*)elements, (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_n_tuple(ar, len, sizes));

    return 0;
}

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:

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]

Permutation algorithm

To find the next permutation of an array ar:

  1. Find the highest index, i1 such that ar[i1] 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 i2, such that i2 > i1 and ar[i2] > ar[i1].
  3. Swap ar[i1] and ar[i2].
  4. The elements from ar[i1 + 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:

#include <stdio.h>

#include <permutation.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2, 3};
    const unsigned int n = sizeof(numbers) / sizeof(unsigned int);
    
    do {
        MBprint_array(numbers, n, stdout);
        putchar('\n');
    } while (MBnext_permutation(numbers, n));

    return 0;
}

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

#include <stdio.h>

#include <permutation.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2, 3};
    char *elements[] = {"a", "b", "c", "d"};
    const unsigned int n = sizeof(numbers) / sizeof(unsigned int);
    
    do {
        MBprint_set(numbers, n, (void*)elements, "[]", (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_permutation(numbers, n));

    return 0;
}

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

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

The set of all combinations 0 ≤ kn 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:

#include <stdio.h>

#include <combination.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    unsigned int n = 5;

    do {
        MBprint_array(numbers, k, stdout);
        putchar('\n');
    } while (MBnext_combination(numbers, n, k));

    return 0;
}

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

#include <stdio.h>

#include <combination.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2};
    char *elements[] = {"a", "b", "c", "d", "e"};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        MBprint_set(numbers, k, (void*)elements, "[]", (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_combination(numbers, n, k));

    return 0;
}

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

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 0, 3]
[0, 1, 1]
[0, 1, 2]
[0, 1, 3]
[0, 2, 2]
[0, 2, 3]
[0, 3, 3]
[1, 1, 1]
[1, 1, 2]
[1, 1, 3]
[1, 2, 2]
[1, 2, 3]
[1, 3, 3]
[2, 2, 2]
[2, 2, 3]
[2, 3, 3]
[3, 3, 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:

#include <stdio.h>

#include <multicombination.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 0, 0};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    unsigned int n = 4;

    do {
        MBprint_array(numbers, k, stdout);
        putchar('\n');
    } while (MBnext_multicombination(numbers, n, k));

    return 0;
}

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:

[0, 1, 1, 2]
[0, 1, 1, 3]
[0, 1, 2, 2]
[0, 1, 2, 3]
[0, 2, 2, 2]
[0, 2, 2, 3]
[1, 1, 2, 2]
[1, 1, 2, 3]
[1, 2, 2, 2]
[1, 2, 2, 3]
[2, 2, 2, 3]

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:

#include <stdio.h>

#include <multiset-combination.h>
#include <comb-util.h>

int main(void)
{
    unsigned int multiset[] = {0, 1, 1, 2, 2, 2, 3};
    unsigned int n = sizeof(multiset) / sizeof(unsigned int);
    unsigned int numbers[] = {0, 1, 1, 2};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);

    do {
        MBprint_array(numbers, k, stdout);
        putchar('\n');
    } while (MBnext_multiset_combination(multiset, numbers, n, k));

    return 0;
}

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

#include <stdio.h>

#include <multiset-combination.h>
#include <util.h>

int main(void)
{
    unsigned int multiset[] = {0, 1, 1, 2, 2, 2, 3};
    char *elements[] = {"a", "b", "c", "d"};
    unsigned int n = sizeof(multiset) / sizeof(unsigned int);
    unsigned int numbers[] = {0, 1, 1, 2};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);

    do {
        MBprint_set(numbers, k, (void*)elements, "[]", (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_multiset_combination(multiset, numbers, n, k));

    return 0;
}

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:

[]
[c]
[b]
[b, c]
[b, b]
[b, b, c]
[a]
[a, c]
[a, b]
[a, b, c]
[a, b, b]
[a, b, b, c]

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:

[0, 0, 0] = []
[0, 0, 1] = [c]
[0, 1, 0] = [b]
[0, 1, 1] = [b, c]
[0, 2, 0] = [b, b]
[0, 2, 1] = [b, b, c]
[1, 0, 0] = [a]
[1, 0, 1] = [a, c]
[1, 1, 0] = [a, b]
[1, 1, 1] = [a, b, c]
[1, 2, 0] = [a, b, b]
[1, 2, 1] = [a, b, b, c]

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

#include <stdio.h>

#include <multiset-subset.h>
#include <comb-util.h>

int main(void)
{
    unsigned int multiset[] = {1, 2, 1};
    unsigned int n = sizeof(multiset) / sizeof(unsigned int);
    unsigned int numbers[] = {0, 0, 0};

    do {
        MBprint_array(numbers, n, stdout);
        putchar('\n');
    } while (MBnext_multiset_subset(multiset, numbers, n));

    return 0;
}

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:

#include <stdio.h>

#include <multiset-subset.h>
#include <comb-util.h>

int main(void)
{
    unsigned int multiset[] = {1, 2, 1};
    unsigned int n = sizeof(multiset) / sizeof(unsigned int);
    char *elements[] = {"a", "b", "c"};
    unsigned int numbers[] = {0, 0, 0};

    do {
        MBprint_multiset_subset(numbers, n, (void*)elements, (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_multiset_subset(multiset, numbers, n));

    return 0;
}

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

[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[0, 1, 3]
[0, 3, 1]
[1, 0, 3]
[1, 3, 0]
[3, 0, 1]
[3, 1, 0]
[0, 2, 3]
[0, 3, 2]
[2, 0, 3]
[2, 3, 0]
[3, 0, 2]
[3, 2, 0]
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

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:

#include <stdio.h>

#include <k-permutation.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    unsigned int n = 4;

    do {
        MBprint_array(numbers, k, stdout);
        putchar('\n');
    } while (MBnext_k_permutation(numbers, n, k));

    return 0;
}

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

#include <stdio.h>

#include <k-permutation.h>
#include <comb-util.h>

int main(void)
{
    unsigned int numbers[] = {0, 1, 2};
    char *elements[] = {"a", "b", "c", "d"};
    const unsigned int k = sizeof(numbers) / sizeof(unsigned int);
    const unsigned int n = sizeof(elements) / sizeof(const char*);

    do {
        MBprint_set(numbers, k, (void*)elements, "[]", (MBprintfn)fputs, stdout);
        putchar('\n');
    } while (MBnext_k_permutation(numbers, n, k));

    return 0;
}

Source code

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

Copyright (C) 2010 Martin Broadhurst