Go to the first, previous, next, last section, table of contents.

This chapter describes functions for creating and manipulating combinations. A combination c is represented by an array of k integers in the range 0 to n-1, where each value c_i occurs at most once. The combination c corresponds to indices of k elements chosen from an n element vector. Combinations are useful for iterating over all k-element subsets of a set.

The functions described in this chapter are defined in the header file
``gsl_combination.h'`.

A combination is defined by a structure containing three components, the
values of n and k, and a pointer to the combination array.
The elements of the combination array are all of type `size_t`

, and
are stored in increasing order. The `gsl_combination`

structure
looks like this,

typedef struct { size_t n; size_t k; size_t *data; } gsl_combination;

__Function:__gsl_combination ***gsl_combination_alloc***(size_t*`n`, size_t`k`)-
This function allocates memory for a new combination with parameters
`n`,`k`. The combination is not initialized and its elements are undefined. Use the function`gsl_combination_calloc`

if you want to create a combination which is initialized to the lexicographically first combination. A null pointer is returned if insufficient memory is available to create the combination.

__Function:__gsl_combination ***gsl_combination_calloc***(size_t*`n`, size_t`k`)-
This function allocates memory for a new combination with parameters
`n`,`k`and initializes it to the lexicographically first combination. A null pointer is returned if insufficient memory is available to create the combination.

__Function:__void**gsl_combination_init_first***(gsl_combination **`c`)-
This function initializes the combination
`c`to the lexicographically first combination, i.e. (0,1,2,...,k-1).

__Function:__void**gsl_combination_init_last***(gsl_combination **`c`)-
This function initializes the combination
`c`to the lexicographically last combination, i.e. (n-k,n-k+1,...,n-1).

__Function:__void**gsl_combination_free***(gsl_combination **`c`)-
This function frees all the memory used by the combination
`c`.

__Function:__int**gsl_combination_memcpy***(gsl_combination **`dest`, const gsl_combination *`src`)-
This function copies the elements of the combination
`src`into the combination`dest`. The two combinations must have the same size.

The following function can be used to access the elements of a combination.

__Function:__size_t**gsl_combination_get***(const gsl_combination **`c`, const size_t`i`)-
This function returns the value of the
`i`-th element of the combination`c`. If`i`lies outside the allowed range of 0 to`k`-1 then the error handler is invoked and 0 is returned. @inlinefn{}

__Function:__size_t**gsl_combination_n***(const gsl_combination **`c`)-
This function returns the range (n) of the combination
`c`.

__Function:__size_t**gsl_combination_k***(const gsl_combination **`c`)-
This function returns the number of elements (k) in the combination
`c`.

__Function:__size_t ***gsl_combination_data***(const gsl_combination **`c`)-
This function returns a pointer to the array of elements in the
combination
`c`.

__Function:__int**gsl_combination_valid***(gsl_combination **`c`)-
This function checks that the combination
`c`is valid. The`k`elements should lie in the range 0 to`n`-1, with each value occurring once at most and in increasing order.

__Function:__int**gsl_combination_next***(gsl_combination **`c`)-
This function advances the combination
`c`to the next combination in lexicographic order and returns`GSL_SUCCESS`

. If no further combinations are available it returns`GSL_FAILURE`

and leaves`c`unmodified. Starting with the first combination and repeatedly applying this function will iterate through all possible combinations of a given order.

__Function:__int**gsl_combination_prev***(gsl_combination **`c`)-
This function steps backwards from the combination
`c`to the previous combination in lexicographic order, returning`GSL_SUCCESS`

. If no previous combination is available it returns`GSL_FAILURE`

and leaves`c`unmodified.

The library provides functions for reading and writing combinations to a file as binary data or formatted text.

__Function:__int**gsl_combination_fwrite***(FILE **`stream`, const gsl_combination *`c`)-
This function writes the elements of the combination
`c`to the stream`stream`in binary format. The function returns`GSL_EFAILED`

if there was a problem writing to the file. Since the data is written in the native binary format it may not be portable between different architectures.

__Function:__int**gsl_combination_fread***(FILE **`stream`, gsl_combination *`c`)-
This function reads elements from the open stream
`stream`into the combination`c`in binary format. The combination`c`must be preallocated with correct values of n and k since the function uses the size of`c`to determine how many bytes to read. The function returns`GSL_EFAILED`

if there was a problem reading from the file. The data is assumed to have been written in the native binary format on the same architecture.

__Function:__int**gsl_combination_fprintf***(FILE **`stream`, const gsl_combination *`c`, const char *`format`)-
This function writes the elements of the combination
`c`line-by-line to the stream`stream`using the format specifier`format`, which should be suitable for a type of`size_t`. In ISO C99 the type modifier`z`

represents`size_t`

, so`"%zu\n"`

is a suitable format.(10) The function returns`GSL_EFAILED`

if there was a problem writing to the file.

__Function:__int**gsl_combination_fscanf***(FILE **`stream`, gsl_combination *`c`)-
This function reads formatted data from the stream
`stream`into the combination`c`. The combination`c`must be preallocated with correct values of n and k since the function uses the size of`c`to determine how many numbers to read. The function returns`GSL_EFAILED`

if there was a problem reading from the file.

The example program below prints all subsets of the set {0,1,2,3} ordered by size. Subsets of the same size are ordered lexicographically.

#include <stdio.h> #include <gsl/gsl_combination.h> int main (void) { gsl_combination * c; size_t i; printf ("All subsets of {0,1,2,3} by size:\n") ; for (i = 0; i <= 4; i++) { c = gsl_combination_calloc (4, i); do { printf ("{"); gsl_combination_fprintf (stdout, c, " %u"); printf (" }\n"); } while (gsl_combination_next (c) == GSL_SUCCESS); gsl_combination_free (c); } return 0; }

Here is the output from the program,

$ ./a.out All subsets of {0,1,2,3} by size: { } { 0 } { 1 } { 2 } { 3 } { 0 1 } { 0 2 } { 0 3 } { 1 2 } { 1 3 } { 2 3 } { 0 1 2 } { 0 1 3 } { 0 2 3 } { 1 2 3 } { 0 1 2 3 }

All 16 subsets are generated, and the subsets of each size are sorted lexicographically.

Further information on combinations can be found in,

- Donald L. Kreher, Douglas R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, 1998, CRC Press LLC, ISBN 084933988X

Go to the first, previous, next, last section, table of contents.