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 .. n1, where each value
c_i is from the range 0 .. n1 and 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
kelement subsets of a set.
The functions described in this chapter are defined in the header file
`gsl_combination.h'.
A combination is stored 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,...,k1).
 Function: void gsl_combination_init_last (gsl_combination * c)

This function initializes the combination c to the
lexicographically last combination, i.e. (nk,nk+1,...,n1).
 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 sizes.
The following function can be used to access combinations elements.
 Function: size_t gsl_combination_get (const gsl_combination * c, const size_t i)

This function returns the value of the ith element of the
combination c. If i lies outside the allowed range of 0 to
k1 then the error handler is invoked and 0 is returned.
 Function: size_t gsl_combination_n (const gsl_combination * c)

This function returns the n parameter of the combination c.
 Function: size_t gsl_combination_k (const gsl_combination * c)

This function returns the k parameter of 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 contain numbers from range 0 .. n1, each number
at most once. The numbers have to be 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 into the combination c from the open stream
stream 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
linebyline to the stream stream using the format specifier
format, which should be suitable for a type of size_t. On a
GNU system the type modifier
Z
represents size_t
, so
"%Zu\n"
is a suitable format. 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
{1,2,3,4} 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,
bash$ ./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

Donald E. Knuth, The Art of Computer Programming: Combinatorial
Algorithms (Vol 4, prefascicle 2c)
http://wwwcsfaculty.stanford.edu/~knuth/fasc2c.ps.gz
Go to the first, previous, next, last section, table of contents.