src/parsec/disk-image/parsec/parsec-benchmark/pkgs/libs/gsl/src/doc/combination.texi - public/gem5-resources - Git at Google

 @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
	@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