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
11 The functions described in this chapter are defined in the header file
12 @file{gsl_combination.h}.
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::
25 @node The Combination struct
26 @section The Combination struct
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
46 @node Combination allocation
47 @section Combination allocation
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.
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.
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)}.
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)}.
75 @deftypefun void gsl_combination_free (gsl_combination * @var{c})
76 This function frees all the memory used by the combination @var{c}.
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.
85 @node Accessing combination elements
86 @section Accessing combination elements
88 The following function can be used to access the elements of a combination.
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{}
96 @node Combination properties
97 @section Combination properties
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}.
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}.
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
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.
120 @node Combination functions
121 @section Combination functions
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.
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.
141 @node Reading and writing combinations
142 @section Reading and writing combinations
144 The library provides functions for reading and writing combinations to a
145 file as binary data or formatted text.
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.
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.
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.
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.
185 @node Combination 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.
192 @verbatiminclude examples/combination.c
196 Here is the output from the program,
200 @verbatiminclude examples/combination.out
204 All 16 subsets are generated, and the subsets of each size are sorted
208 @node Combination References and Further Reading
209 @section References and Further Reading
212 Further information on combinations can be found in,
216 Donald L. Kreher, Douglas R. Stinson, @cite{Combinatorial Algorithms:
217 Generation, Enumeration and Search}, 1998, CRC Press LLC, ISBN