~ubuntu-branches/ubuntu/dapper/gsl-ref-html/dapper : contents of gsl-ref

~ubuntu-branches/ubuntu/dapper/gsl-ref-html/dapper : (revision 4)
<HTML>
<HEAD>
<!-- This HTML file has been created by texi2html 1.54+ (gsl)
     from /home/bjg/gsl.redhat/doc/gsl-ref.texi on 14 September 2005 -->

<TITLE>GNU Scientific Library -- Reference Manual - Combinations</TITLE>
<link href="gsl-ref_11.html" rel=Next>
<link href="gsl-ref_9.html" rel=Previous>
<link href="gsl-ref_toc.html" rel=ToC>

</HEAD>
<BODY>
<p>Go to the <A HREF="gsl-ref_1.html">first</A>, <A HREF="gsl-ref_9.html">previous</A>, <A HREF="gsl-ref_11.html">next</A>, <A HREF="gsl-ref_50.html">last</A> section, <A HREF="gsl-ref_toc.html">table of contents</A>.
<P><HR><P>


<H1><A NAME="SEC199" HREF="gsl-ref_toc.html#TOC199">Combinations</A></H1>
<P>
<A NAME="IDX986"></A>

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

</P>
<P>
The functions described in this chapter are defined in the header file
<TT>`gsl_combination.h'</TT>.

</P>



<H2><A NAME="SEC200" HREF="gsl-ref_toc.html#TOC200">The Combination struct</A></H2>

<P>
A combination is defined by a structure containing three components, the
values of n and k, and a pointer to the combination array.
The elements of the combination array are all of type <CODE>size_t</CODE>, and
are stored in increasing order.  The <CODE>gsl_combination</CODE> structure
looks like this,

</P>

<PRE>
typedef struct
{
  size_t n;
  size_t k;
  size_t *data;
} gsl_combination;
</PRE>

<P>

</P>


<H2><A NAME="SEC201" HREF="gsl-ref_toc.html#TOC201">Combination allocation</A></H2>

<P>
<DL>
<DT><U>Function:</U> gsl_combination * <B>gsl_combination_alloc</B> <I>(size_t <VAR>n</VAR>, size_t <VAR>k</VAR>)</I>
<DD><A NAME="IDX987"></A>
This function allocates memory for a new combination with parameters
<VAR>n</VAR>, <VAR>k</VAR>.  The combination is not initialized and its elements
are undefined.  Use the function <CODE>gsl_combination_calloc</CODE> 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.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> gsl_combination * <B>gsl_combination_calloc</B> <I>(size_t <VAR>n</VAR>, size_t <VAR>k</VAR>)</I>
<DD><A NAME="IDX988"></A>
This function allocates memory for a new combination with parameters
<VAR>n</VAR>, <VAR>k</VAR> and initializes it to the lexicographically first
combination. A null pointer is returned if insufficient memory is
available to create the combination.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> void <B>gsl_combination_init_first</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX989"></A>
This function initializes the combination <VAR>c</VAR> to the
lexicographically first combination, i.e.  (0,1,2,...,k-1).
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> void <B>gsl_combination_init_last</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX990"></A>
This function initializes the combination <VAR>c</VAR> to the
lexicographically last combination, i.e.  (n-k,n-k+1,...,n-1).
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> void <B>gsl_combination_free</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX991"></A>
This function frees all the memory used by the combination <VAR>c</VAR>.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_memcpy</B> <I>(gsl_combination * <VAR>dest</VAR>, const gsl_combination * <VAR>src</VAR>)</I>
<DD><A NAME="IDX992"></A>
This function copies the elements of the combination <VAR>src</VAR> into the
combination <VAR>dest</VAR>.  The two combinations must have the same size.
</DL>

</P>



<H2><A NAME="SEC202" HREF="gsl-ref_toc.html#TOC202">Accessing combination elements</A></H2>

<P>
The following function can be used to access the elements of a combination.

</P>
<P>
<DL>
<DT><U>Function:</U> size_t <B>gsl_combination_get</B> <I>(const gsl_combination * <VAR>c</VAR>, const size_t <VAR>i</VAR>)</I>
<DD><A NAME="IDX993"></A>
This function returns the value of the <VAR>i</VAR>-th element of the
combination <VAR>c</VAR>.  If <VAR>i</VAR> lies outside the allowed range of 0 to
<VAR>k</VAR>-1 then the error handler is invoked and 0 is returned.
</DL>

</P>


<H2><A NAME="SEC203" HREF="gsl-ref_toc.html#TOC203">Combination properties</A></H2>

<P>
<DL>
<DT><U>Function:</U> size_t <B>gsl_combination_n</B> <I>(const gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX994"></A>
This function returns the range (n) of the combination <VAR>c</VAR>.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> size_t <B>gsl_combination_k</B> <I>(const gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX995"></A>
This function returns the number of elements (k) in the combination <VAR>c</VAR>.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> size_t * <B>gsl_combination_data</B> <I>(const gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX996"></A>
This function returns a pointer to the array of elements in the
combination <VAR>c</VAR>.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_valid</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX997"></A>
<A NAME="IDX998"></A>
<A NAME="IDX999"></A>
This function checks that the combination <VAR>c</VAR> is valid.  The <VAR>k</VAR>
elements should lie in the range 0 to <VAR>n</VAR>-1, with each
value occurring once at most and in increasing order.
</DL>

</P>


<H2><A NAME="SEC204" HREF="gsl-ref_toc.html#TOC204">Combination functions</A></H2>

<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_next</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX1000"></A>
<A NAME="IDX1001"></A>
This function advances the combination <VAR>c</VAR> to the next combination
in lexicographic order and returns <CODE>GSL_SUCCESS</CODE>.  If no further
combinations are available it returns <CODE>GSL_FAILURE</CODE> and leaves
<VAR>c</VAR> unmodified.  Starting with the first combination and
repeatedly applying this function will iterate through all possible
combinations of a given order.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_prev</B> <I>(gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX1002"></A>
This function steps backwards from the combination <VAR>c</VAR> to the
previous combination in lexicographic order, returning
<CODE>GSL_SUCCESS</CODE>.  If no previous combination is available it returns
<CODE>GSL_FAILURE</CODE> and leaves <VAR>c</VAR> unmodified.
</DL>

</P>



<H2><A NAME="SEC205" HREF="gsl-ref_toc.html#TOC205">Reading and writing combinations</A></H2>

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

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_fwrite</B> <I>(FILE * <VAR>stream</VAR>, const gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX1003"></A>
This function writes the elements of the combination <VAR>c</VAR> to the
stream <VAR>stream</VAR> in binary format.  The function returns
<CODE>GSL_EFAILED</CODE> 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.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_fread</B> <I>(FILE * <VAR>stream</VAR>, gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX1004"></A>
This function reads elements from the open stream <VAR>stream</VAR> into the
combination <VAR>c</VAR> in binary format.  The combination <VAR>c</VAR> must be
preallocated with correct values of n and k since the
function uses the size of <VAR>c</VAR> to determine how many bytes to read.
The function returns <CODE>GSL_EFAILED</CODE> 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.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_fprintf</B> <I>(FILE * <VAR>stream</VAR>, const gsl_combination * <VAR>c</VAR>, const char * <VAR>format</VAR>)</I>
<DD><A NAME="IDX1005"></A>
This function writes the elements of the combination <VAR>c</VAR>
line-by-line to the stream <VAR>stream</VAR> using the format specifier
<VAR>format</VAR>, which should be suitable for a type of <VAR>size_t</VAR>.  On a
GNU system the type modifier <CODE>Z</CODE> represents <CODE>size_t</CODE>, so
<CODE>"%Zu\n"</CODE> is a suitable format.  The function returns
<CODE>GSL_EFAILED</CODE> if there was a problem writing to the file.
</DL>

</P>
<P>
<DL>
<DT><U>Function:</U> int <B>gsl_combination_fscanf</B> <I>(FILE * <VAR>stream</VAR>, gsl_combination * <VAR>c</VAR>)</I>
<DD><A NAME="IDX1006"></A>
This function reads formatted data from the stream <VAR>stream</VAR> into the
combination <VAR>c</VAR>.  The combination <VAR>c</VAR> must be preallocated with
correct values of n and k since the function uses the size of <VAR>c</VAR> to
determine how many numbers to read.  The function returns
<CODE>GSL_EFAILED</CODE> if there was a problem reading from the file.
</DL>

</P>



<H2><A NAME="SEC206" HREF="gsl-ref_toc.html#TOC206">Examples</A></H2>
<P>
The example program below prints all subsets of the set
{0,1,2,3} ordered by size.  Subsets of the same size are
ordered lexicographically.

</P>

<PRE>
#include &#60;stdio.h&#62;
#include &#60;gsl/gsl_combination.h&#62;

int 
main (void) 
{
  gsl_combination * c;
  size_t i;

  printf ("All subsets of {0,1,2,3} by size:\n") ;
  for (i = 0; i &#60;= 4; i++)
    {
      c = gsl_combination_calloc (4, i);
      do
        {
          printf ("{");
          gsl_combination_fprintf (stdout, c, " %u");
          printf (" }\n");
        }
      while (gsl_combination_next (c) == GSL_SUCCESS);
      gsl_combination_free (c);
    }

  return 0;
}
</PRE>

<P>
Here is the output from the program,

</P>

<PRE>
$ ./a.out 
All subsets of {0,1,2,3} by size:
{ }
{ 0 }
{ 1 }
{ 2 }
{ 3 }
{ 0 1 }
{ 0 2 }
{ 0 3 }
{ 1 2 }
{ 1 3 }
{ 2 3 }
{ 0 1 2 }
{ 0 1 3 }
{ 0 2 3 }
{ 1 2 3 }
{ 0 1 2 3 }
</PRE>

<P>
All 16 subsets are generated, and the subsets of each size are sorted
lexicographically.

</P>



<H2><A NAME="SEC207" HREF="gsl-ref_toc.html#TOC207">References and Further Reading</A></H2>

<P>
Further information on combinations can be found in,

</P>

<UL>
<LI>

Donald L. Kreher, Douglas R. Stinson, <CITE>Combinatorial Algorithms:
Generation, Enumeration and Search</CITE>, 1998, CRC Press LLC, ISBN
084933988X
</UL>

<P>

</P>

<P><HR><P>
<p>Go to the <A HREF="gsl-ref_1.html">first</A>, <A HREF="gsl-ref_9.html">previous</A>, <A HREF="gsl-ref_11.html">next</A>, <A HREF="gsl-ref_50.html">last</A> section, <A HREF="gsl-ref_toc.html">table of contents</A>.
</BODY>
</HTML>