Go to the first, previous, next, last section, table of contents.

Combinations

This chapter describes functions for creating and manipulating combinations. A combination c is represented by an array of k integers in the range 0 .. n-1, where each value c_i is from the range 0 .. n-1 and 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.

The functions described in this chapter are defined in the header file `gsl_combination.h'.

The Combination struct

A combination is stored 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 size_t, and are stored in increasing order. The gsl_combination structure looks like this,

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

Combination allocation

Function: gsl_combination * gsl_combination_alloc (size_t n, size_t k)

This function allocates memory for a new combination with parameters n, k. The combination is not initialized and its elements are undefined. Use the function 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.

Function: gsl_combination * gsl_combination_calloc (size_t n)

This function allocates memory for a new combination with parameters n, k and initializes it to the lexicographically first combination. A null pointer is returned if insufficient memory is available to create the combination.

Function: void gsl_combination_init_first (gsl_combination * c)

This function initializes the combination c to the lexicographically first combination, i.e. (0,1,2,...,k-1).

Function: void gsl_combination_init_last (gsl_combination * c)

This function initializes the combination c to the lexicographically last combination, i.e. (n-k,n-k+1,...,n-1).

Function: void gsl_combination_free (gsl_combination * c)

This function frees all the memory used by the combination c.

Accessing combination elements

The following function can be used to access combinations elements.

Function: size_t gsl_combination_get (const gsl_combination * c, const size_t i)

This function returns the value of the i-th element of the combination c. If i lies outside the allowed range of 0 to k-1 then the error handler is invoked and 0 is returned.

Combination properties

Function: size_t gsl_combination_n (const gsl_combination * c)

This function returns the n parameter of the combination c.

Function: size_t gsl_combination_k (const gsl_combination * c)

This function returns the k parameter of the combination c.

Function: size_t * gsl_combination_data (const gsl_combination * c)

This function returns a pointer to the array of elements in the combination c.

Function: int gsl_combination_valid (gsl_combination * c)

This function checks that the combination c is valid. The k elements should contain numbers from range 0 .. n-1, each number at most once. The numbers have to be in increasing order.

Combination functions

Function: int gsl_combination_next (gsl_combination * c)

This function advances the combination c to the next combination in lexicographic order and returns GSL_SUCCESS. If no further combinations are available it returns GSL_FAILURE and leaves c unmodified. Starting with the fisrst combination and repeatedly applying this function will iterate through all possible combinations of a given order.

Function: int gsl_combination_prev (gsl_combination * c)

This function steps backwards from the combination c to the previous combination in lexicographic order, returning GSL_SUCCESS. If no previous combination is available it returns GSL_FAILURE and leaves c unmodified.

Reading and writing combinations

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

Function: int gsl_combination_fwrite (FILE * stream, const gsl_combination * c)

This function writes the elements of the combination 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_combination_fread (FILE * stream, gsl_combination * c)

This function reads into the combination c from the open stream stream in binary format. The combination 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_combination_fprintf (FILE * stream, const gsl_combination * c, const char *format)

This function writes the elements of the combination c line-by-line to the stream stream using the format specifier format, which should be suitable for a type of size_t. On a GNU system the type modifier Z represents size_t, so "%Zu\n" is a suitable format. The function returns GSL_EFAILED if there was a problem writing to the file.

Function: int gsl_combination_fscanf (FILE * stream, gsl_combination * c)

This function reads formatted data from the stream stream into the combination c. The combination 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 subsets of the set {1,2,3,4} ordered by size. Subsets of the same size are ordered lexicographically.

#include <stdio.h>
#include <gsl/gsl_combination.h>

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

  printf("All subsets of {0,1,2,3} by size:\n") ;
  for(i = 0; i <= 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;
}

Here is the output from the program,

bash$ ./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 }

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

Go to the first, previous, next, last section, table of contents.