SELECT
Nijenhuis and Wilf
Combinatorial Selection Algorithm


SELECT is a FORTRAN90 library which implements the Nijenhuis and Wilf Combinatorial Selection Algorithm.

In the reference, Nijenhuis and Wilf presented particular algorithms to rank, unrank, enumerate, sequentially generate, or randomly generate objects from a variety of combinatorial families, such as K-subsets of an N-set, permutations, partitions, and so on.

In the course of this development, they come across a number of cases where, to determine the number B(N,K) of objects of size K in a family of maximum size N, a recurrence is used of the form

B(N,K) = PHI(N,K) * B(N1,K1) + PSI(N,K) * B(N2,K2)
Typically, but not always, it is the case that:
        N1 = N - 1
        N2 = N - 1
        K1 = K
        K2 = K - 1
      
and the values of the coefficient functions PHI and PSI depended on the family.

This pattern suggested that a single abstract approach could be used to carry out the usual tasks for a variety of combinatorial families. The result was a subroutine called SELECT which while not optimized for a particular family, displays their common underlying structure, and allows new families to be added easily.

The combinatorial families are indicated by the value of the variable FAMILY, and characterized by a "big" size N and a smaller size K:

  1. K subsets of an N set;
  2. Partitions of N objects into K classes;
  3. Permutations of N objects with K cycles;
  4. Vector subspaces of dimension K over N-dimensional space over the field of order Q (where Q is currently set to 2 );
  5. Permutations of N letters with K runs;
  6. Partitions of N whose largest part is K;
  7. Compositions of N into K parts.

The combinatorial tasks, indicated by the value of the variable TASK, include

  1. Present each object of the family, one at a time.
  2. Rank a given object of the family.
  3. Produce an object of given rank.
  4. Select an object at random.
  5. Enumerate the objects.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

SELECT is available in a FORTRAN77 version and a FORTRAN90 version.

Related Data and Programs:

COMBO, a FORTRAN90 library which carries out various combinatorial tasks.

LAMP, a FORTRAN77 library which solves linear assignment and matching problems.

SUBSET, a FORTRAN90 library which contains the individual Nijenhuis and Wilf routines.

Reference:

  1. Albert Nijenhuis, Herbert Wilf,
    Combinatorial Algorithms,
    Academic Press, 1978, second edition.

Source Code:

Examples and Tests:

List of Routines:

You can go up one level to the FORTRAN90 source codes.


Last revised on 30 August 2005.