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.

The Combination struct
======================

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;

Combination allocation
======================

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

Accessing combination elements
==============================

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.

Combination properties
======================

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

Combination functions
=====================

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

Reading and writing combinations
================================

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

Examples
========

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.

          [file combination.c not included]

Here is the output from the program,

     $ ./a.out
          [file combination.out not included]

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

References and Further Reading
==============================

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