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:

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

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

Present each object of the family, one at a time.
Rank a given object of the family.
Produce an object of given rank.
Select an object at random.
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 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:

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

Source Code:

select.f90, the source code.

Examples and Tests:

select_test.f90, a sample calling program.
select_test.txt, the output file.

List of Routines:

BNEW returns either of two values needed to compute B(N,K).
CODE_TO_COMPOSITION decodes a composition.
CODE_TO_PARTITION_NUM decodes a numeric partition.
CODE_TO_PARTITION_SET decodes a set partition.
CODE_TO_PERM_CYCLE decodes a permutation of N objects with K cycles.
CODE_TO_PERM_RUNS decodes a permutation of N objects with K runs.
CODE_TO_SUBSET decodes a subset.
CODE_TO_SUBSPACE decodes a subspace.
COMPOSITION_TO_STRING writes a character representation of a composition.
DIGIT_TO_CH returns the character representation of a decimal digit.
FAMILY_ENUMERATE produces an enumeration table for a given family.
FAMILY_NEXT carries out a task for a combinatorial family of order N, K.
FAMILY_RANK returns the rank of an object of a given family.
FAMILY_SAMPLE produces a sample object of a given family.
FAMILY_UNRANK produces an object of given rank of a given family.
I4_TO_S_LEFT converts an integer to a left-justified string.
I4_UNIFORM returns a scaled pseudorandom I4.
I4MAT_PRINT prints an integer matrix.
I4MAT_PRINT_SOME prints some of an integer matrix.
I4VEC_PRINT prints an integer vector.
PARTITION_NUM_TO_STRING represents a numeric partition.
PARTITION_SET_TO_STRING writes a character representation of a set partition.
PERM_CYCLE_TO_STRING makes a string out of a permutation in cycle form.
PHI returns the coefficient PHI(N,K) in the recurrence.
PSI returns the coefficient PSI(N,K) in the recurrence.
R8_UNIFORM_01 returns a unit pseudorandom R8.
SELECT carries out a task for a combinatorial family of order N, K.
SUBSET_TO_STRING writes a character representation of a subset.
TIMESTAMP prints the current YMDHMS date as a time stamp.
XNEW returns an index for the recursive enumeration of a family.

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

Last revised on 30 August 2005.

SELECT Nijenhuis and Wilf Combinatorial Selection Algorithm