SELECT
Nijenhuis and Wilf
Combinatorial Selection Algorithm

SELECT is a FORTRAN77 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)

        N1 = N - 1
        N2 = N - 1
        K1 = K
        K2 = K - 1
      

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.

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

Reference:

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

Source Code:

• select.f, the source code.
• select.sh, commands to compile the source code.

Examples and Tests:

• select_prb.f, a sample calling program.
• select_prb.sh, commands to compile and run the sample program.
• select_prb_output.txt, the output from a run of the sample program.

List of Routines:

• BNEW returns either of two values needed to compute B(N,K).
• PHI returns the coefficient PHI(N,K) in the recurrence.
• PSI returns the coefficient PSI(N,K) in the recurrence.
• SELECT carries out a task for a combinatorial family of order N, K.
• XNEW returns an index for the recursive enumeration of a family.

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