# Combinatorial Algorithms

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

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

• Find the rightmost 1 with a 0 on its right. If it exists:
1. Move it one cell to the right
2. Move all of the 1s on its right, which are packed on the right hand side, to the cells immediately behind it
• Otherwise, If all of the 1s are on the right hand side and ar[0] is 0, add another 1 and move the other 1s immediately behind it
• Otherwise, all subsets have been produced, so return the array to its starting arrangement of all 0s

#### 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 using Gray codes

#### Introduction

When calculations are being performed on each element of the power set, it can be advantageous if each set differs from its predecessor by as few elements as possible. One can produce the subsets in order such that each subset differs from its predecessor by only one element. The characteristic vectors of sets in this order are called Gray codes.

These are the Gray codes in order for a set of 3 elements:

[0, 0, 0]
[1, 0, 0]
[1, 1, 0]
[0, 1, 0]
[0, 1, 1]
[1, 1, 1]
[1, 0, 1]
[0, 0, 1]

They correspond to the following subsets. Notice how each subset differs from its predecessor by only 1 element:

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

#### Gray code algorithm

In order to go from one Gray code to its successor, it is necessary to find which single value in the array to change from 1 to 0, or vice-versa.

The rules for finding the index of this element j are based on the number of 1s in the current code, k, as follows:

• If k is even, then j = 0
• If k is odd, then j is the index of the first cell that follows the first 1

#### Examples

The following program produces the characteristic vectors for the power set of a 3-set in Gray code order:

```#include <stdio.h>

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

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

do {
MBprint_array(ar, n, stdout);
putchar('\n');
} while (MBnext_subset_gray(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-gray.h>
#include <comb-util.h>

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

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

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.

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

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

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

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

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

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

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

#### 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;
}