htswanalysis/MACS/lib/gsl/gsl-1.11/doc/combination.texi

   1 @cindex combinations
   2
   3 This chapter describes functions for creating and manipulating
   4 combinations. A combination @math{c} is represented by an array of
   5 @math{k} integers in the range 0 to @math{n-1}, where each value
   6 @math{c_i} occurs at most once.  The combination @math{c} corresponds to
   7 indices of @math{k} elements chosen from an @math{n} element vector.
   8 Combinations are useful for iterating over all @math{k}-element subsets
   9 of a set.
  10
  11 The functions described in this chapter are defined in the header file
  12 @file{gsl_combination.h}.
  13
  14 @menu
  15 * The Combination struct::
  16 * Combination allocation::
  17 * Accessing combination elements::
  18 * Combination properties::
  19 * Combination functions::
  20 * Reading and writing combinations::
  21 * Combination Examples::
  22 * Combination References and Further Reading::
  23 @end menu
  24
  25 @node The Combination struct
  26 @section The Combination struct
  27
  28 A combination is defined by a structure containing three components, the
  29 values of @math{n} and @math{k}, and a pointer to the combination array.
  30 The elements of the combination array are all of type @code{size_t}, and
  31 are stored in increasing order.  The @code{gsl_combination} structure
  32 looks like this,
  33
  34 @example
  35 typedef struct
  36 @{
  37   size_t n;
  38   size_t k;
  39   size_t *data;
  40 @} gsl_combination;
  41 @end example
  42 @comment
  43
  44 @noindent
  45
  46 @node Combination allocation
  47 @section Combination allocation
  48
  49 @deftypefun {gsl_combination *} gsl_combination_alloc (size_t @var{n}, size_t @var{k})
  50 This function allocates memory for a new combination with parameters
  51 @var{n}, @var{k}.  The combination is not initialized and its elements
  52 are undefined.  Use the function @code{gsl_combination_calloc} if you
  53 want to create a combination which is initialized to the
  54 lexicographically first combination. A null pointer is returned if
  55 insufficient memory is available to create the combination.
  56 @end deftypefun
  57
  58 @deftypefun {gsl_combination *} gsl_combination_calloc (size_t @var{n}, size_t @var{k})
  59 This function allocates memory for a new combination with parameters
  60 @var{n}, @var{k} and initializes it to the lexicographically first
  61 combination. A null pointer is returned if insufficient memory is
  62 available to create the combination.
  63 @end deftypefun
  64
  65 @deftypefun void gsl_combination_init_first (gsl_combination * @var{c})
  66 This function initializes the combination @var{c} to the
  67 lexicographically first combination, i.e.  @math{(0,1,2,@dots{},k-1)}.
  68 @end deftypefun
  69
  70 @deftypefun void gsl_combination_init_last (gsl_combination * @var{c})
  71 This function initializes the combination @var{c} to the
  72 lexicographically last combination, i.e.  @math{(n-k,n-k+1,@dots{},n-1)}.
  73 @end deftypefun
  74
  75 @deftypefun void gsl_combination_free (gsl_combination * @var{c})
  76 This function frees all the memory used by the combination @var{c}.
  77 @end deftypefun
  78
  79 @deftypefun int gsl_combination_memcpy (gsl_combination * @var{dest}, const gsl_combination * @var{src})
  80 This function copies the elements of the combination @var{src} into the
  81 combination @var{dest}.  The two combinations must have the same size.
  82 @end deftypefun
  83
  84
  85 @node Accessing combination elements
  86 @section Accessing combination elements
  87
  88 The following function can be used to access the elements of a combination.
  89
  90 @deftypefun size_t gsl_combination_get (const gsl_combination * @var{c}, const size_t @var{i})
  91 This function returns the value of the @var{i}-th element of the
  92 combination @var{c}.  If @var{i} lies outside the allowed range of 0 to
  93 @math{@var{k}-1} then the error handler is invoked and 0 is returned.  @inlinefn{}
  94 @end deftypefun
  95
  96 @node Combination properties
  97 @section Combination properties
  98
  99 @deftypefun size_t gsl_combination_n (const gsl_combination * @var{c})
 100 This function returns the range (@math{n}) of the combination @var{c}.
 101 @end deftypefun
 102
 103 @deftypefun size_t gsl_combination_k (const gsl_combination * @var{c})
 104 This function returns the number of elements (@math{k}) in the combination @var{c}.
 105 @end deftypefun
 106
 107 @deftypefun {size_t *} gsl_combination_data (const gsl_combination * @var{c})
 108 This function returns a pointer to the array of elements in the
 109 combination @var{c}.
 110 @end deftypefun
 111
 112 @deftypefun int gsl_combination_valid (gsl_combination * @var{c})
 113 @cindex checking combination for validity
 114 @cindex testing combination for validity
 115 This function checks that the combination @var{c} is valid.  The @var{k}
 116 elements should lie in the range 0 to @math{@var{n}-1}, with each
 117 value occurring once at most and in increasing order.
 118 @end deftypefun
 119
 120 @node Combination functions
 121 @section Combination functions
 122
 123 @deftypefun int gsl_combination_next (gsl_combination * @var{c})
 124 @cindex iterating through combinations
 125 This function advances the combination @var{c} to the next combination
 126 in lexicographic order and returns @code{GSL_SUCCESS}.  If no further
 127 combinations are available it returns @code{GSL_FAILURE} and leaves
 128 @var{c} unmodified.  Starting with the first combination and
 129 repeatedly applying this function will iterate through all possible
 130 combinations of a given order.
 131 @end deftypefun
 132
 133 @deftypefun int gsl_combination_prev (gsl_combination * @var{c})
 134 This function steps backwards from the combination @var{c} to the
 135 previous combination in lexicographic order, returning
 136 @code{GSL_SUCCESS}.  If no previous combination is available it returns
 137 @code{GSL_FAILURE} and leaves @var{c} unmodified.
 138 @end deftypefun
 139
 140
 141 @node Reading and writing combinations
 142 @section Reading and writing combinations
 143
 144 The library provides functions for reading and writing combinations to a
 145 file as binary data or formatted text.
 146
 147 @deftypefun int gsl_combination_fwrite (FILE * @var{stream}, const gsl_combination * @var{c})
 148 This function writes the elements of the combination @var{c} to the
 149 stream @var{stream} in binary format.  The function returns
 150 @code{GSL_EFAILED} if there was a problem writing to the file.  Since the
 151 data is written in the native binary format it may not be portable
 152 between different architectures.
 153 @end deftypefun
 154
 155 @deftypefun int gsl_combination_fread (FILE * @var{stream}, gsl_combination * @var{c})
 156 This function reads elements from the open stream @var{stream} into the
 157 combination @var{c} in binary format.  The combination @var{c} must be
 158 preallocated with correct values of @math{n} and @math{k} since the
 159 function uses the size of @var{c} to determine how many bytes to read.
 160 The function returns @code{GSL_EFAILED} if there was a problem reading
 161 from the file.  The data is assumed to have been written in the native
 162 binary format on the same architecture.
 163 @end deftypefun
 164
 165 @deftypefun int gsl_combination_fprintf (FILE * @var{stream}, const gsl_combination * @var{c}, const char * @var{format})
 166 This function writes the elements of the combination @var{c}
 167 line-by-line to the stream @var{stream} using the format specifier
 168 @var{format}, which should be suitable for a type of @var{size_t}.
 169 In ISO C99 the type modifier @code{z} represents @code{size_t}, so
 170 @code{"%zu\n"} is a suitable format.@footnote{In versions of the
 171 GNU C library prior to the ISO C99 standard,
 172 the type modifier @code{Z} was used instead.}  The function returns
 173 @code{GSL_EFAILED} if there was a problem writing to the file.
 174 @end deftypefun
 175
 176 @deftypefun int gsl_combination_fscanf (FILE * @var{stream}, gsl_combination * @var{c})
 177 This function reads formatted data from the stream @var{stream} into the
 178 combination @var{c}.  The combination @var{c} must be preallocated with
 179 correct values of @math{n} and @math{k} since the function uses the size of @var{c} to
 180 determine how many numbers to read.  The function returns
 181 @code{GSL_EFAILED} if there was a problem reading from the file.
 182 @end deftypefun
 183
 184
 185 @node Combination Examples
 186 @section Examples
 187 The example program below prints all subsets of the set
 188 @math{@{0,1,2,3@}} ordered by size.  Subsets of the same size are
 189 ordered lexicographically.
 190
 191 @example
 192 @verbatiminclude examples/combination.c
 193 @end example
 194
 195 @noindent
 196 Here is the output from the program,
 197
 198 @example
 199 $ ./a.out
 200 @verbatiminclude examples/combination.out
 201 @end example
 202
 203 @noindent
 204 All 16 subsets are generated, and the subsets of each size are sorted
 205 lexicographically.
 206
 207
 208 @node Combination References and Further Reading
 209 @section References and Further Reading
 210
 211 @noindent
 212 Further information on combinations can be found in,
 213
 214 @itemize @asis
 215 @item
 216 Donald L. Kreher, Douglas R. Stinson, @cite{Combinatorial Algorithms:
 217 Generation, Enumeration and Search}, 1998, CRC Press LLC, ISBN
 218 084933988X
 219 @end itemize
 220
 221 @noindent
 222
 223