This chapter describes functions for creating and manipulating multisets. A multiset c is represented by an array of k integers in the range 0 to n-1, where each value c_i may occur more than once.  The multiset c corresponds to indices of k elements chosen from an n element vector with replacement.  In mathematical terms, n is the cardinality of the multiset while k is the maximum multiplicity of any value.  Multisets are useful, for example, when iterating over the indices of a k-th order symmetric tensor in n-space.

The functions described in this chapter are defined in the header file gsl_multiset.h.

The Multiset struct
===================

A multiset is defined by a structure containing three components, the values of n and k, and a pointer to the multiset array. The elements of the multiset array are all of type size_t, and are stored in increasing order.  The gsl_multiset structure looks like this,

     typedef struct
     {
       size_t n;
       size_t k;
       size_t *data;
     } gsl_multiset;

Multiset allocation
===================

 -- Function: gsl_multiset * gsl_multiset_alloc (size_t N, size_t K)
     This function allocates memory for a new multiset with parameters N, K.  The multiset is not initialized and its elements are undefined.  Use the function gsl_multiset_calloc if you want to create a multiset which is initialized to the lexicographically first multiset element. A null pointer is returned if insufficient memory is available to create the multiset.

 -- Function: gsl_multiset * gsl_multiset_calloc (size_t N, size_t K)
     This function allocates memory for a new multiset with parameters N, K and initializes it to the lexicographically first multiset element. A null pointer is returned if insufficient memory is available to create the multiset.

 -- Function: void gsl_multiset_init_first (gsl_multiset * C)
     This function initializes the multiset C to the lexicographically first multiset element, i.e. 0 repeated k times.

 -- Function: void gsl_multiset_init_last (gsl_multiset * C)
     This function initializes the multiset C to the lexicographically last multiset element, i.e. n-1 repeated k times.

 -- Function: void gsl_multiset_free (gsl_multiset * C)
     This function frees all the memory used by the multiset C.

 -- Function: int gsl_multiset_memcpy (gsl_multiset * DEST, const gsl_multiset * SRC)
     This function copies the elements of the multiset SRC into the multiset DEST.  The two multisets must have the same size.

Accessing multiset elements
===========================

The following function can be used to access the elements of a multiset.

 -- Function: size_t gsl_multiset_get (const gsl_multiset * C, const size_t I)
     This function returns the value of the I-th element of the multiset C.  If I lies outside the allowed range of 0 to K-1 then the error handler is invoked and 0 is returned.  inlinefn

Multiset properties
===================

 -- Function: size_t gsl_multiset_n (const gsl_multiset * C)
     This function returns the range (n) of the multiset C.

 -- Function: size_t gsl_multiset_k (const gsl_multiset * C)
     This function returns the number of elements (k) in the multiset C.

 -- Function: size_t * gsl_multiset_data (const gsl_multiset * C)
     This function returns a pointer to the array of elements in the multiset C.

 -- Function: int gsl_multiset_valid (gsl_multiset * C)
     This function checks that the multiset C is valid.  The K elements should lie in the range 0 to N-1, with each value occurring in nondecreasing order.

Multiset functions
==================

 -- Function: int gsl_multiset_next (gsl_multiset * C)
     This function advances the multiset C to the next multiset element in lexicographic order and returns GSL_SUCCESS.  If no further multisets elements are available it returns GSL_FAILURE and leaves C unmodified.  Starting with the first multiset and repeatedly applying this function will iterate through all possible multisets of a given order.

 -- Function: int gsl_multiset_prev (gsl_multiset * C)
     This function steps backwards from the multiset C to the previous multiset element in lexicographic order, returning GSL_SUCCESS.  If no previous multiset is available it returns GSL_FAILURE and leaves C unmodified.

Reading and writing multisets
=============================

The library provides functions for reading and writing multisets to a file as binary data or formatted text.

 -- Function: int gsl_multiset_fwrite (FILE * STREAM, const gsl_multiset * C)
     This function writes the elements of the multiset C to the stream STREAM in binary format.  The function returns 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.

 -- Function: int gsl_multiset_fread (FILE * STREAM, gsl_multiset * C)
     This function reads elements from the open stream STREAM into the multiset C in binary format.  The multiset C must be preallocated with correct values of n and k since the function uses the size of C to determine how many bytes to read. The function returns 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.

 -- Function: int gsl_multiset_fprintf (FILE * STREAM, const gsl_multiset * C, const char * FORMAT)
     This function writes the elements of the multiset C line-by-line to the stream STREAM using the format specifier FORMAT, which should be suitable for a type of SIZE_T. In ISO C99 the type modifier z represents size_t, so "%zu\n" is a suitable format. (In versions of the GNU C library prior to the ISO C99 standard, the type modifier Z was used instead.)  The function returns GSL_EFAILED if there was a problem writing to the file.

 -- Function: int gsl_multiset_fscanf (FILE * STREAM, gsl_multiset * C)
     This function reads formatted data from the stream STREAM into the multiset C.  The multiset C must be preallocated with correct values of n and k since the function uses the size of C to determine how many numbers to read.  The function returns GSL_EFAILED if there was a problem reading from the file.

Examples
========

The example program below prints all multisets elements containing the values {0,1,2,3} ordered by size.  Multiset elements of the same size are ordered lexicographically.

          [file multiset.c not included]

Here is the output from the program,

     $ ./a.out
          [file multiset.txt not included]

All 70 multisets are generated and sorted lexicographically.