select

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)

        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 MIT license

Languages:

select is available in a Fortran77 version and a Fortran90 version.

Related Data and Programs:

select_test

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.