combination.texi

GNU Scientific Library,C语言开发的数值方面的函数库

@cindex combinations

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

The functions described in this chapter are defined in the header file
@file{gsl_combination.h}.

@menu
* The Combination struct::      
* Combination allocation::      
* Accessing combination elements::  
* Combination properties::      
* Combination functions::       
* Reading and writing combinations::  
* Combination Examples::        
* Combination References and Further Reading::
@end menu

@node The Combination struct
@section The Combination struct

A combination is stored by a structure containing three components, the
values of @math{n} and @math{k}, and a pointer to the combination array.
The elements of the combination array are all of type @code{size_t}, and
are stored in increasing order.  The @code{gsl_combination} structure
looks like this,

@example
typedef struct
@{
  size_t n;
  size_t k;
  size_t *data;
@} gsl_combination;
@end example
@comment
@noindent

@node Combination allocation
@section Combination allocation

@deftypefun {gsl_combination *} gsl_combination_alloc (size_t @var{n}, size_t @var{k})
This function allocates memory for a new combination with parameters
@var{n}, @var{k}.  The combination is not initialized and its elements
are undefined.  Use the function @code{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.
@end deftypefun

@deftypefun {gsl_combination *} gsl_combination_calloc (size_t @var{n}, size_t @var{k})
This function allocates memory for a new combination with parameters
@var{n}, @var{k} and initializes it to the lexicographically first
combination. A null pointer is returned if insufficient memory is
available to create the combination.
@end deftypefun

@deftypefun void gsl_combination_init_first (gsl_combination * @var{c})
This function initializes the combination @var{c} to the
lexicographically first combination, i.e.  @math{(0,1,2,...,k-1)}.
@end deftypefun

@deftypefun void gsl_combination_init_last (gsl_combination * @var{c})
This function initializes the combination @var{c} to the
lexicographically last combination, i.e.  @math{(n-k,n-k+1,...,n-1)}.
@end deftypefun

@deftypefun void gsl_combination_free (gsl_combination * @var{c})
This function frees all the memory used by the combination @var{c}.
@end deftypefun

@deftypefun int gsl_combination_memcpy (gsl_combination * @var{dest}, const gsl_combination * @var{src})
This function copies the elements of the combination @var{src} into the
combination @var{dest}.  The two combinations must have the same sizes.
@end deftypefun


@node Accessing combination elements
@section Accessing combination elements

The following function can be used to access combinations elements.

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

@node Combination properties
@section Combination properties

@deftypefun size_t gsl_combination_n (const gsl_combination * @var{c})
This function returns the @math{n} parameter of the combination @var{c}.
@end deftypefun

@deftypefun size_t gsl_combination_k (const gsl_combination * @var{c})
This function returns the @math{k} parameter of the combination @var{c}.
@end deftypefun

@deftypefun {size_t *} gsl_combination_data (const gsl_combination * @var{c})
This function returns a pointer to the array of elements in the
combination @var{c}.
@end deftypefun

@deftypefun int gsl_combination_valid (gsl_combination * @var{c})
@cindex checking combination for validity
@cindex testing combination for validity
This function checks that the combination @var{c} is valid.  The @var{k}
elements should contain numbers from range 0 .. @var{n}-1, each number
at most once.  The numbers have to be in increasing order.
@end deftypefun

@node Combination functions
@section Combination functions

@deftypefun int gsl_combination_next (gsl_combination * @var{c})
@cindex iterating through combinations
This function advances the combination @var{c} to the next combination
in lexicographic order and returns @code{GSL_SUCCESS}.  If no further
combinations are available it returns @code{GSL_FAILURE} and leaves
@var{c} unmodified.  Starting with the first combination and
repeatedly applying this function will iterate through all possible
combinations of a given order.
@end deftypefun

@deftypefun int gsl_combination_prev (gsl_combination * @var{c})
This function steps backwards from the combination @var{c} to the
previous combination in lexicographic order, returning
@code{GSL_SUCCESS}.  If no previous combination is available it returns
@code{GSL_FAILURE} and leaves @var{c} unmodified.
@end deftypefun


@node Reading and writing combinations
@section Reading and writing combinations

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

@deftypefun int gsl_combination_fwrite (FILE * @var{stream}, const gsl_combination * @var{c})
This function writes the elements of the combination @var{c} to the
stream @var{stream} in binary format.  The function returns
@code{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.
@end deftypefun

@deftypefun int gsl_combination_fread (FILE * @var{stream}, gsl_combination * @var{c})
This function reads into the combination @var{c} from the open stream
@var{stream} in binary format.  The combination @var{c} must be
preallocated with correct values of @math{n} and @math{k} since the
function uses the size of @var{c} to determine how many bytes to read.
The function returns @code{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.
@end deftypefun

@deftypefun int gsl_combination_fprintf (FILE * @var{stream}, const gsl_combination * @var{c}, const char *@var{format})
This function writes the elements of the combination @var{c}
line-by-line to the stream @var{stream} using the format specifier
@var{format}, which should be suitable for a type of @var{size_t}.  On a
GNU system the type modifier @code{Z} represents @code{size_t}, so
@code{"%Zu\n"} is a suitable format.  The function returns
@code{GSL_EFAILED} if there was a problem writing to the file.
@end deftypefun

@deftypefun int gsl_combination_fscanf (FILE * @var{stream}, gsl_combination * @var{c})
This function reads formatted data from the stream @var{stream} into the
combination @var{c}.  The combination @var{c} must be preallocated with
correct values of @math{n} and @math{k} since the function uses the size of @var{c} to
determine how many numbers to read.  The function returns
@code{GSL_EFAILED} if there was a problem reading from the file.
@end deftypefun


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

@example
@verbatiminclude examples/combination.c
@end example
@noindent
Here is the output from the program,

@example
bash$ ./a.out 
@verbatiminclude examples/combination.out
@end example
@noindent

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


@node Combination References and Further Reading
@section References and Further Reading

Further information on combinations can be found in,

@itemize @asis
@item
Donald L. Kreher, Douglas R. Stinson, @cite{Combinatorial Algorithms:
Generation, Enumeration and Search}, 1998, CRC Press LLC, ISBN
084933988X

@item
Donald E. Knuth, @cite{The Art of Computer Programming: Combinatorial
Algorithms} (Vol 4, pre-fascicle 2c)
@url{http://www-cs-faculty.stanford.edu/~knuth/fasc2c.ps.gz}
@end itemize
@noindent