|
Packit |
67cb25 |
.. index:: combinations
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
************
|
|
Packit |
67cb25 |
Combinations
|
|
Packit |
67cb25 |
************
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: include.rst
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This chapter describes functions for creating and manipulating
|
|
Packit |
67cb25 |
combinations. A combination :math:`c` is represented by an array of
|
|
Packit |
67cb25 |
:math:`k` integers in the range 0 to :math:`n - 1`, where each value
|
|
Packit |
67cb25 |
:math:`c_i` occurs at most once. The combination :math:`c` corresponds to
|
|
Packit |
67cb25 |
indices of :math:`k` elements chosen from an :math:`n` element vector.
|
|
Packit |
67cb25 |
Combinations are useful for iterating over all :math:`k`-element subsets
|
|
Packit |
67cb25 |
of a set.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The functions described in this chapter are defined in the header file
|
|
Packit |
67cb25 |
:file:`gsl_combination.h`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The Combination struct
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. type:: gsl_combination
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
A combination is defined by a structure containing three components, the
|
|
Packit |
67cb25 |
values of :math:`n` and :math:`k`, and a pointer to the combination array.
|
|
Packit |
67cb25 |
The elements of the combination array are all of type :code:`size_t`, and
|
|
Packit |
67cb25 |
are stored in increasing order. The :type:`gsl_combination` structure
|
|
Packit |
67cb25 |
looks like this::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
typedef struct
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t n;
|
|
Packit |
67cb25 |
size_t k;
|
|
Packit |
67cb25 |
size_t *data;
|
|
Packit |
67cb25 |
} gsl_combination;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Combination allocation
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_combination * gsl_combination_alloc (size_t n, size_t k)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates memory for a new combination with parameters
|
|
Packit |
67cb25 |
:data:`n`, :data:`k`. The combination is not initialized and its elements
|
|
Packit |
67cb25 |
are undefined. Use the function :func:`gsl_combination_calloc` if you
|
|
Packit |
67cb25 |
want to create a combination which is initialized to the
|
|
Packit |
67cb25 |
lexicographically first combination. A null pointer is returned if
|
|
Packit |
67cb25 |
insufficient memory is available to create the combination.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_combination * gsl_combination_calloc (size_t n, size_t k)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates memory for a new combination with parameters
|
|
Packit |
67cb25 |
:data:`n`, :data:`k` and initializes it to the lexicographically first
|
|
Packit |
67cb25 |
combination. A null pointer is returned if insufficient memory is
|
|
Packit |
67cb25 |
available to create the combination.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_combination_init_first (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function initializes the combination :data:`c` to the
|
|
Packit |
67cb25 |
lexicographically first combination, i.e. :math:`(0, 1, 2, \dots, k - 1)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_combination_init_last (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function initializes the combination :data:`c` to the
|
|
Packit |
67cb25 |
lexicographically last combination, i.e. :math:`(n - k, n - k + 1, \dots, n - 1)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_combination_free (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function frees all the memory used by the combination :data:`c`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_memcpy (gsl_combination * dest, const gsl_combination * src)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function copies the elements of the combination :data:`src` into the
|
|
Packit |
67cb25 |
combination :data:`dest`. The two combinations must have the same size.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Accessing combination elements
|
|
Packit |
67cb25 |
==============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The following function can be used to access the elements of a combination.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_combination_get (const gsl_combination * c, const size_t i)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the value of the :data:`i`-th element of the
|
|
Packit |
67cb25 |
combination :data:`c`. If :data:`i` lies outside the allowed range of 0 to
|
|
Packit |
67cb25 |
:math:`k - 1` then the error handler is invoked and 0 is returned. |inlinefn|
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Combination properties
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_combination_n (const gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the range (:math:`n`) of the combination c.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_combination_k (const gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the number of elements (:math:`k`) in the combination :data:`c`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t * gsl_combination_data (const gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns a pointer to the array of elements in the
|
|
Packit |
67cb25 |
combination :data:`c`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: checking combination for validity
|
|
Packit |
67cb25 |
single: testing combination for validity
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_valid (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function checks that the combination :data:`c` is valid. The :data:`k`
|
|
Packit |
67cb25 |
elements should lie in the range 0 to :math:`n - 1`, with each
|
|
Packit |
67cb25 |
value occurring once at most and in increasing order.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Combination functions
|
|
Packit |
67cb25 |
=====================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index:: iterating through combinations
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_next (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function advances the combination :data:`c` to the next combination
|
|
Packit |
67cb25 |
in lexicographic order and returns :macro:`GSL_SUCCESS`. If no further
|
|
Packit |
67cb25 |
combinations are available it returns :macro:`GSL_FAILURE` and leaves
|
|
Packit |
67cb25 |
:data:`c` unmodified. Starting with the first combination and
|
|
Packit |
67cb25 |
repeatedly applying this function will iterate through all possible
|
|
Packit |
67cb25 |
combinations of a given order.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_prev (gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function steps backwards from the combination :data:`c` to the
|
|
Packit |
67cb25 |
previous combination in lexicographic order, returning
|
|
Packit |
67cb25 |
:macro:`GSL_SUCCESS`. If no previous combination is available it returns
|
|
Packit |
67cb25 |
:macro:`GSL_FAILURE` and leaves :data:`c` unmodified.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Reading and writing combinations
|
|
Packit |
67cb25 |
================================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The library provides functions for reading and writing combinations to a
|
|
Packit |
67cb25 |
file as binary data or formatted text.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_fwrite (FILE * stream, const gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the combination :data:`c` to the
|
|
Packit |
67cb25 |
stream :data:`stream` in binary format. The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem writing to the file. Since the
|
|
Packit |
67cb25 |
data is written in the native binary format it may not be portable
|
|
Packit |
67cb25 |
between different architectures.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_fread (FILE * stream, gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads elements from the open stream :data:`stream` into the
|
|
Packit |
67cb25 |
combination :data:`c` in binary format. The combination :data:`c` must be
|
|
Packit |
67cb25 |
preallocated with correct values of :math:`n` and :math:`k` since the
|
|
Packit |
67cb25 |
function uses the size of :data:`c` to determine how many bytes to read.
|
|
Packit |
67cb25 |
The function returns :macro:`GSL_EFAILED` if there was a problem reading
|
|
Packit |
67cb25 |
from the file. The data is assumed to have been written in the native
|
|
Packit |
67cb25 |
binary format on the same architecture.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_fprintf (FILE * stream, const gsl_combination * c, const char * format)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the combination :data:`c`
|
|
Packit |
67cb25 |
line-by-line to the stream :data:`stream` using the format specifier
|
|
Packit |
67cb25 |
:data:`format`, which should be suitable for a type of :code:`size_t`.
|
|
Packit |
67cb25 |
In ISO C99 the type modifier :code:`z` represents :code:`size_t`, so
|
|
Packit |
67cb25 |
:code:`"%zu\n"` is a suitable format [#f1]_.
|
|
Packit |
67cb25 |
The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem writing to the file.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_combination_fscanf (FILE * stream, gsl_combination * c)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads formatted data from the stream :data:`stream` into the
|
|
Packit |
67cb25 |
combination :data:`c`. The combination :data:`c` must be preallocated with
|
|
Packit |
67cb25 |
correct values of :math:`n` and :math:`k` since the function uses the size of :data:`c` to
|
|
Packit |
67cb25 |
determine how many numbers to read. The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem reading from the file.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Examples
|
|
Packit |
67cb25 |
========
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The example program below prints all subsets of the set
|
|
Packit |
67cb25 |
:math:`{0,1,2,3}` ordered by size. Subsets of the same size are
|
|
Packit |
67cb25 |
ordered lexicographically.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: examples/combination.c
|
|
Packit |
67cb25 |
:code:
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Here is the output from the program,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: examples/combination.txt
|
|
Packit |
67cb25 |
:code:
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
All 16 subsets are generated, and the subsets of each size are sorted
|
|
Packit |
67cb25 |
lexicographically.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
References and Further Reading
|
|
Packit |
67cb25 |
==============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Further information on combinations can be found in,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
* Donald L. Kreher, Douglas R. Stinson, Combinatorial Algorithms:
|
|
Packit |
67cb25 |
Generation, Enumeration and Search, 1998, CRC Press LLC, ISBN
|
|
Packit |
67cb25 |
084933988X
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. rubric:: Footnotes
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. [#f1] In versions of the GNU C library prior to the ISO C99 standard,
|
|
Packit |
67cb25 |
the type modifier :code:`Z` was used instead.
|