1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
|
@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 to @math{n-1}, where each value
@math{c_i} 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 defined 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,@dots{},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,@dots{},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 size.
@end deftypefun
@node Accessing combination elements
@section Accessing combination elements
The following function can be used to access the elements of a combination.
@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
@math{@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 range (@math{n}) of the combination @var{c}.
@end deftypefun
@deftypefun size_t gsl_combination_k (const gsl_combination * @var{c})
This function returns the number of elements (@math{k}) in 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 lie in the range 0 to @math{@var{n}-1}, with each
value occurring once at most and 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 elements from the open stream @var{stream} into the
combination @var{c} 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
$ ./a.out
@verbatiminclude examples/combination.out
@end example
@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
@noindent
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
@end itemize
@noindent
|
