select, a Fortran77 code 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 - 1and 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:
The combinatorial tasks, indicated by the value of the variable TASK, include
The computer code and data files described and made available on this web page are distributed under the MIT license
select is available in a Fortran77 version and a Fortran90 version.
combo, a Fortran90 library which carries out various combinatorial tasks.
SUBSET, a Fortran77 library which contains the individual Nijenhuis and Wilf routines.